Self-routing superconcentrators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Self-routing superconcentrators

Full text

Pdf (769 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 355 - 361

Year of Publication: 1993

ISBN:0-89791-591-7

Author

Nicholas Pippenger

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 4

Additional Information:

references cited by 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/167088.167195 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.

	1	N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
	4	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	5	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
	6	S. Arora, T. Leighton and B. Maggs, "On-Line Algorithms for Path Selection in a Nonblocking Network", preprint,.
	7	K. E. Batcher, "Sorting Networks and Their Applications", Proc. AFIPS Spring Joint Computer Conf., 32 (1968) 307-314.
	8	O. Gabber and Z. Galil, "Explicit Constructions of Linear-Sized Superconcentrators", J. Comp. and Sys. Sci., 22 (1981) 407-420.
	9	J. E. Hopcroft and R. M. Karp, "An n5/2 Algorithm for Maximal Matchngs in Bipartitte Graphs", SIAM J. Computing, 2 (1975) 225-231.
	10	Shuji Jimbo , Akira Maruoka, Expanders obtained from affine transformations, Combinatorica, v.7 n.4, p.343-355, Dec, 1987 [doi>10.1007/BF02579322]
	11	T. Leighton and B. Maggs, "Expanders Might Be Practical: Fast Algorithms for Routing around " " IEEE Syrup. on Foun- Faults on Multibutterflms , dations of Computer Science, 30 (1989) 384-389.
	12	A. Lubotzky, R. Phillips and P. Sarnak, "Ramanujan Graphs", Combinatorica, 8 (1988) 261- 277.
	13	G. A.Margulis, "Explicit Construction of Concentrators", Problems of Inform. Transm., 9 (197.4) 71-80.
	14	G. A. Margulis, "Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators", Problems of Inform. Transm., 24 (1988) 39-46.
	15	David Peleg , Eli Upfal, The token distribution problem, SIAM Journal on Computing, v.18 n.2, p.229-243, April 1989 [doi>10.1137/0218015]
	16	M. S. Pinsker, "On the Complexity of a Concentrator", Internat. Teletraffic Congr., 7 (1973) 318/1-318/4.
	17	N. Pippenger, "Superconcentrators", SIAM J. Computing, 6 (1977) 298-304.
	18	N. Pippenger, "On Networks of Noisy Gates", IEEE Symp. on Foundations of Computer Science, 26 (1985) 30-38.
	19	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
	20	L. G. Valiant, "Graph-Theoretic Properties in Computational Complexity", J. Comp. and S'ys. Sci., 13 (1976) 278-285.

CITED BY 4

	Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.388-397, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Pierre Kelsen, Fast parallel matching in expander graphs, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.293-299, June 30-July 02, 1993, Velen, Germany
	Nabil Kahale, Eigenvalues and expansion of regular graphs, Journal of the ACM (JACM), v.42 n.5, p.1091-1106, Sept. 1995
	Eric A. Brewer , Frederic T. Chong , Tom Leighton, Scalable expanders: exploiting hierarchical random wiring, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.144-152, May 23-25, 1994, Montreal, Quebec, Canada