Color-coding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Color-coding

Full text

Pdf (1.03 MB)

Source

Journal of the ACM (JACM) archive
Volume 42 , Issue 4 (July 1995) table of contents

Pages: 844 - 856

Year of Publication: 1995

ISSN:0004-5411

Authors

Noga Alon	Institute for Advanced Study, Princeton, NJ; and Tel-Aviv Univ., Tel-Aviv, Israel
Raphael Yuster	Tel-Aviv Univ., Tel-Aviv, Israel
Uri Zwick	Tel-Aviv Univ., Tel-Aviv, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 32, Downloads (12 Months): 164, Citation Count: 37

Additional Information:

references cited by index terms review 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/210332.210337 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	~ALON, N., BRUCK, J., NAOR, J., NAOR, M., AND ROTH, R.M. 1992. Construction of asymptoti- ~cally good low-rate error-correcting codes through pseudo-random graphs. 1EEE Trcms. hzf. ~Theory 38, 2, 509-516.
	2	~ALON, N., GOLDREICH, O., Hz~,STAD, J., AND PERAI,TA, R. 1992/1993. Simple constructions of ~almost k-wise independent random variab}{es. Random Struct. Algorifhms 3, 3, (1992), 289-304. ~(Addendum in Random Struct. Algorithms, 4, 1, (1993), 11%120).
	3	~ALON, N., AND NAOR, M. Dcrandomlzation, witnesses for boolean matrix multiphcation and ~construction of perfect has functions. Algo~ith,zica, to appear.
	4	~ALON, N., YUSTER, R., AND ZWICK, U. Finding and counting given length cycles. SL4M J. Disc. ~Math. to appear.
	5	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]
	6	~BOLLOB,~S. B. 1978. Extremal graph theoJy. Academic Press, Orlando, Fla.
	7	~BOLLOB,~S, B. 1986. Extremal graph theol~ with e,lpha,slS ott probabilistic methods. Regional ~conference series in mathematics, No. 62. American Mathematical Society, Providence. R.I.
	8	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]
	9	~CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R.L. 1992. hztroduction to Algorzth,zs. The MIT ~Press, Cambridge, Mass.
	10	~DOWNEY, R. G. AND FELLOWS, M.R. 1992. FLxed-parameter lntractabihty. In Proceedings of ~the 7th Annual Sympo~tu,t o~z S,ztcture m Complexity Theory (Boston, Mass.). IEEE, Los ~Alamltos, Cahf., pp. 36-49.
	11	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
	12	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]
	13	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
	14	~ITAI, A, AND RODEH, M. 1978. Finding a minimum circuit in a graph. SlAM J. Comput. 7, ~413 423.
	15	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]
	16	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
	17	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]
	18	~MONIEN, B. 1985. How to find long paths efficiently. Ann. Disc. Math. 25, 239 254.
	19	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]
	20	~P~,PADJM;rmOU, C. H. AND YANNAKAKIS, M 1981 The clique problem for planar graphs, blf ~Proc. Lett. 13, 131-133.
	21	~PAPADIMITRIOU, C. H. AND Y4.NNAIO\KIS, U. 1993. On hmlted nondeterminism and the com- ~plex~ty of the V-C dimension. In Proceedings of the 8th Annual Sympo3tum on Structure m ~ComplexlO' Theory (San Diego, Calif.'). IEEE, Los Alamitos, Calif., pp. 12-18.
	22	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
	23	~RICIIARDS, D. 1986. Finding short cycles in a planar graph using separators. J. Algorzthms 7, ~382 394.
	24	~ROBERTSON, N., AND SEYMOUR, P. 1986a. Graph minors. II. Algorithmic aspects of tree-width ~J. Algorithms 7, 309-322.
	25	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]
	26	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]
	27	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 37

	Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.12-19, May 11-15, 1997, Tucson, Arizona, United States
	Harold N. Gabow, Finding paths and cycles of superpolylogarithmic length, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Stuart Campbell , Mohan Kumar , Horst Bunke, Parallel subgraph matching on a hierarchical interconnection network, Hardware implementation of intelligent systems, Physica-Verlag GmbH, Heidelberg, Germany, 2001
	Harold N. Gabow , Shuxin Nie, Finding a long directed cycle, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Friedrich Eisenbrand , Fabrizio Grandoni, Detecting directed 4-cycles still faster, Information Processing Letters, v.87 n.1, p.13-15, 16 July 2003
	Raphael Yuster , Uri Zwick, Detecting short directed cycles using rectangular matrix multiplication and dynamic programming, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Sundar Vishwanathan, An approximation algorithm for finding long paths in Hamiltonian graphs, Journal of Algorithms, v.50 n.2, p.246-256, February 2004
	Parinya Chalermsook , Jittat Fakcharoenphol , Danupon Nanongkai, A deterministic near-linear time algorithm for finding minimum cuts in planar graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Raphael Yuster , Uri Zwick, Fast sparse matrix multiplication, ACM Transactions on Algorithms (TALG), v.1 n.1, p.2-13, July 2005
	Markus Bläser, Computing small partial coverings, Information Processing Letters, v.85 n.6, p.327-331, 31 March 2003
	Ioannis Koutis, A faster parameterized algorithm for set packing, Information Processing Letters, v.94 n.1, p.7-9, 15 April 2005
	Yana Kortsarts , Jeffrey Rufinus, How (and why) to introduce Monte Carlo randomized algorithms into a basic algorithms course?, Journal of Computing Sciences in Colleges, v.21 n.2, p.195-203, December 2005
	Martin Grohe , Dániel Marx, Constraint solving via fractional edge covers, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.289-298, January 22-26, 2006, Miami, Florida
	Virginia Vassilevska , Ryan Williams , Shan Leung Maverick Woo, Confronting hardness using a hybrid approach, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1-10, January 22-26, 2006, Miami, Florida
	Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, v.348 n.2, p.357-365, 8 December 2005
	Elena Prieto , Christian Sloper, Looking at the stars, Theoretical Computer Science, v.351 n.3, p.437-445, 28 February 2006
	Maurizio Bruglieri , Matthias Ehrgott , Horst W. Hamacher , Francesco Maffioli, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Discrete Applied Mathematics, v.154 n.9, p.1344-1357, 1 June 2006
	Noga Alon , Dana Moshkovitz , Shmuel Safra, Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), v.2 n.2, p.153-177, April 2006
	Virginia Vassilevska , Ryan Williams, Finding a maximum weight triangle in n^3-Δ time, with applications, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Ralf Borndörfer , Martin Grötschel , Marc E. Pfetsch, A Column-Generation Approach to Line Planning in Public Transport, Transportation Science, v.41 n.1, p.123-132, February 2007
	Jaroslav Nešetřil , Patrice Ossona de Mendez, Linear time low tree-width partitions and algorithmic consequences, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Andreas Björklund , Thore Husfeldt , Petteri Kaski , Mikko Koivisto, Fourier meets möbius: fast subset convolution, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Noga Alon , Andrzej Lingas , Martin Wahlen, Approximating the maximum clique minor and some subgraph homeomorphism problems, Theoretical Computer Science, v.374 n.1-3, p.149-158, April, 2007
	Timothy M. Chan, More algorithms for all-pairs shortest paths in weighted graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Frederic Dorn , Fedor V. Fomin , Dimitrios M. Thilikos, Catalan structures and dynamic programming in H-minor-free graphs, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.631-640, January 20-22, 2008, San Francisco, California
	Ryan Williams, Finding paths of length k in O∗(2k) time, Information Processing Letters, v.109 n.6, p.315-318, February, 2009
	Jianer Chen , Songjian Lu , Sing-Hoi Sze , Fenghui Zhang, Improved algorithms for path, matching, and packing problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.298-307, January 07-09, 2007, New Orleans, Louisiana
	Gerhard J. Woeginger, Open problems around exact algorithms, Discrete Applied Mathematics, v.156 n.3, p.397-405, February, 2008
	Jaroslav Nešetřil , Patrice Ossona de Mendez, Grad and classes with bounded expansion II. Algorithmic aspects, European Journal of Combinatorics, v.29 n.3, p.777-791, April, 2008
	Harold N. Gabow , Shuxin Nie, Finding a long directed cycle, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-21, March 2008
	Artur Czumaj , Andrzej Lingas, Finding a heaviest triangle is not harder than matrix multiplication, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.986-994, January 07-09, 2007, New Orleans, Louisiana
	Dana Angluin , James Aspnes , Jiang Chen , Lev Reyzin, Learning large-alphabet and analog circuits with value injection queries, Machine Learning, v.72 n.1-2, p.113-138, August 2008
	Dániel Marx , Marcus Schaefer, The complexity of nonrepetitive coloring, Discrete Applied Mathematics, v.157 n.1, p.13-18, January, 2009
	Michael R. Fellows , Danny Hermelin , Frances Rosamond , Stéphane Vialette, On the parameterized complexity of multiple-interval graph problems, Theoretical Computer Science, v.410 n.1, p.53-61, January, 2009
	Virginia Vassilevska, Efficient algorithms for clique problems, Information Processing Letters, v.109 n.4, p.254-257, January, 2009
	Andrzej Lingas , Eva-Marta Lundell, Efficient approximation algorithms for shortest cycles in undirected graphs, Information Processing Letters, v.109 n.10, p.493-498, April, 2009
	Virginia Vassilevska , Ryan Williams, Finding, minimizing, and counting weighted subgraphs, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Path and circuit problems

Additional Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.1.3 Complexity Measures and Classes

G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS
G.2.2 Graph Theory
Subjects: Graph algorithms

General Terms:
Algorithms

Keywords:
derandomization, perfect hashing, subgraph isomorphism, tree-width

REVIEW

"Adam Drozdek : Reviewer"

A color-coding method in which the vertices of a graph are randomly colored using k colors is introduced. The method was originally intended to design algorithms for finding paths and cycles. Using more...

Collaborative Colleagues:

Noga Alon: colleagues

Raphael Yuster: colleagues

Uri Zwick: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player