Color-coding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs

Full text

Pdf (994 KB)

Source

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

Montreal, Quebec, Canada

Pages: 326 - 335

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Noga Alon	Institute for Advanced study, School of Mathematics, Princeton, NJ and School of Mathematical Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Raphy Yuster	School of Mathematical Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel
Uri Zwick	School of Mathematical Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 39, Citation Count: 7

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/195058.195179 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.

	ABN+92	N. Alon, J. Bruck, J. Naor, M. Naor, and R.M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38(2):509-516, 1992.
	AGHP92	N. Alon, O. Goldreich, J. H~stad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289-304, 1992. Addendum in Random Structures and Algorithms, 4(1 ):119-120, 1993.
	AN94	N. Alon and M. Naor. Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. To appear in Algorithmica, 1994.
	Bod93	Hans L. Bodlaender, On linear time minor tests with depth-first search, Journal of Algorithms, v.14 n.1, p.1-23, Jan. 1993 [doi>10.1006/jagm.1993.1001]
	Bol78	Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
	Bol86	B. Bollob~s. Extremal graph theory with emphasis on probabilistic methods. Regional conference series in mathematics, No. 62, American Mathematical Society, 1986.
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	CN85	Norishige Chiba , Takao Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, v.14 n.1, p.210-223, Feb. 1985 [doi>10.1137/0214017]
	DF92	R.G. Downey and M.R. Fellows. Fixedparameter intractability. In Proceedings of the 7th Annual Symposium on Structure in Complexity Theory, pages 36- 49, 1992.
	FKS84	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	FR92	Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
	IR78	A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM Journal on Computing, 7:413-423, 1978.
	Joh87	David S. Johnson, The NP-completeness column: an ongoing guide, Journal of Algorithms, v.8 n.2, p.285-303, June 1987 [doi>10.1016/0196-6774(87)90043-5]
	KMR93	David R. Karger , Rajeev Motwani , G. D. S. Ramkumar, On Approximating the Longest Path in a Graph (Preliminary Version), Proceedings of the Third Workshop on Algorithms and Data Structures, p.421-432, August 11-13, 1993
	MB83	David W. Matula , Leland L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, Journal of the ACM (JACM), v.30 n.3, p.417-427, July 1983 [doi>10.1145/2402.322385]
	Mon85	B. Monien. How to find long paths efficiently. Annals of Discrete Mathematics, 25:239-254, 1985.
	NN90	J. Naor , M. Naor, Small-bias probability spaces: efficient constructions and applications, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.213-223, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100244]
	PV90	Jürgen Plehn , Bernd Voigt, Finding minimally weighted subgraphs, Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.18-29, May 1991, Berlin, Germany
	PY81	C.H. Papadimitriou and M. Yannakakis. The clique problem for planar graphs. Information Processing Letters, 13:131-133, 1981.
	PY93	C.H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. In Proceedings of the 8th Annual Symposium on Structure in Complexity Theory, San Diego, California, pages 12-18, 1993.
	Ric86	D. Richards. Finding short cycles in a planar graph using separators. Journal of Algorithms, 7:382-394, 1986.
	RS86a	N. Robertson and P. Seymour. Graph minors. II. Algorithmic aspects of treewidth. Journal of Algorithms, 7:309- 322, 1986.
	RS86b	Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
	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]
	YZ94	Raphael Yuster , Uri Zwick, Finding Even Cycles Even Faster, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, p.532-543, July 11-14, 1994

CITED BY 7

	Sundar Vishwanathan, An approximation algorithm for finding a long path in Hamiltonian graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.680-685, January 09-11, 2000, San Francisco, California, United States
	David Eppstein, Subgraph isomorphism in planar graphs and related problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.632-640, January 22-24, 1995, San Francisco, California, United States
	Tomas Feder , Rajeev Motwani , Carlos Subi, Finding long paths and cycles in sparse Hamiltonian graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.524-529, May 21-23, 2000, Portland, Oregon, United States
	Marcelo Oglietti, Understanding planning with incomplete information and sensing, Artificial Intelligence, v.164 n.1-2, p.171-208, May 2005
	Béla Csaba , Marek Karpinski , Piotr Krysta, Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.74-83, January 06-08, 2002, San Francisco, California
	Muhammad Adeel Talib , Zongkai Yang , Qazi Mudassar Ilyas, A framework towards web services composition modelling and execution, International Journal of Web and Grid Services, v.2 n.1, p.25-49, February 2006
	Zhao Zhang , Hao Li, Algorithms for long paths in graphs, Theoretical Computer Science, v.377 n.1-3, p.25-34, May, 2007