Space-efficient routing in vertex-symmetric networks (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Space-efficient routing in vertex-symmetric networks (extended abstract)

Full text

Pdf (958 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Barbara, California, United States

Pages: 137 - 146

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Friedhelm Meyer auf der Heide	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany
Christian Scheideler	Department of Mathematics and Computer Science and Heinz Nixdorf Institute, University of Paderborn, 33095 Paderborn, Germany

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/215399.215433 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ABLP90	Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
	B93	V. Braune. Theoret#sche und ezperimentelle Analyse yon Intervall-Routing-Algorithmen. Muster Thesis, Department of Mathematics and Computer Science, University of Paderborn, 1993.
	FGS93	Michele Flammini , Giorgio Gambosi , Sandro Salomone, Boolean Routing, Proceedings of the 7th International Workshop on Distributed Algorithms, p.219-233, September 27-29, 1993
	FJ88	G.N. Frederickson and R. Janardan. Designing Networks with Compact Routing Tables. Algorithmzca 3, pp. 171-190, 1988.
	FJ90	Greg N. Frederickson , Ravi Janardan, Space-efficient message routing in c-decomposable networks, SIAM Journal on Computing, v.19 n.1, p.164-181, Feb. 1990 [doi>10.1137/0219011]
	L92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	LPS88	A. Lubotzky, R. Phillips, R. Sarnak. Ramanujan Graphs. Comb#natorica 8/3, pp. 261-277, 1988.
	LMRR94	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	M88	G.A. Margulis. Explicit Group Theoretical Constructions of Combinatorial Schemes and their Application to the Design of Expanders and Superconcentrators. Problems Inform. Transmission 11, pp. 39-46, 1988.
	M94	Moshe Morgenstern, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, Journal of Combinatorial Theory Series B, v.62 n.1, p.44-62, Sept. 1994 [doi>10.1006/jctb.1994.1054]
	MV95	F. Meyer auf der Heide and B. V5cking. A Packet Routing Protocol for Arbitrary Networks. In 12th Syrup. on Theoretzcal Aspects of Computer Science (STACS 95), pp. 291-302, 1995.
	PU89	David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
	R91	Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
	SS90	Jeanette P. Schmidt , Alan Siegel, The spatial complexity of oblivious k-probe Hash functions, SIAM Journal on Computing, v.19 n.5, p.775-786, Oct. 1990 [doi>10.1137/0219054]
	SSS93	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
	V82	L.G. Valiant. A Scheme for Fast Parallel Communication. SIAM Journal of Computing 11/2, pp. 350-361, 1982.