Finding paths and cycles of superpolylogarithmic length

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Finding paths and cycles of superpolylogarithmic length

Full text

Pdf (252 KB)

Source

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

Chicago, IL, USA

SESSION: Session 11A table of contents

Pages: 407 - 416

Year of Publication: 2004

ISBN:1-58113-852-0

Author

Harold N. Gabow

University of Colorado at Boulder, Boulder, CO

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 42, Citation Count: 8

Additional Information:

abstract 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/1007352.1007418 What is a DOI?

ABSTRACT

Let l be the number of edges in a longest cycle containing a given vertex v in an undirected graph. We show how to find a cycle through v of length (Ω(√ log l, log log l)) in polynomial time. This implies the same bound for the longest cycle, longest vw-path and longest path. The previous best bound for longest path is length Ω((log l )²/, log log l) due to Björklund and Husfeldt. Our approach, which builds on Björklund and Husfeldt's, uses cycles to enlarge cycles. This self-reducibility allows the approximation method to be iterated.

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	Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
	2	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]
	3	Andreas Björklund , Thore Husfeldt, Finding a Path of Superlogarithmic Length, SIAM Journal on Computing, v.32 n.6, p.1395-1402, 2003 [doi>10.1137/S0097539702416761]
	4	A. Björklund, T. Husfeldt and S. Khanna, Approximating longest directed path, Electronic Colloq. on Comp. Complexity, Rept. No. 32, 2003.
	5	Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
	6	Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
	7	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
	8	J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2,3 (1973), pp. 135--158.
	9	D. Karger, R. Motwani and G. D. S. Ramkumar, On approximating the longest path in a graph, Algorithmica 18 (1997), pp. 82--98.
	10	A. S. LaPaugh and R. L. Rivest, The subgraph homeomorphism problem, J. Comput. Sys. Sci. 20 (1980), pp. 133--149.
	11	B. Monien, How to find long paths efficiently, Annals Disc. Math., 25 (1985), pp. 239--254.
	12	Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
	13	R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146--160.
	14	D. B. West, Introduction to Graph Theory, 2nd Ed., Prentice Hall (2001).

CITED BY 8

	Tomás Feder , Rajeev Motwani, Finding large cycles in Hamiltonian graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	Gopal Pandurangan, On a simple randomized algorithm for finding a 2-factor in sparse graphs, Information Processing Letters, v.95 n.1, p.321-327, 16 July 2005
	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
	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
	Ken-ichi Kawarabayashi , Bruce Reed, A nearly linear time algorithm for the half integral disjoint paths packing, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.446-454, January 20-22, 2008, San Francisco, California
	Yoshihiro Takahara , Sachio Teramoto , Ryuhei Uehara, Longest Path Problems on Ptolemaic Graphs, IEICE - Transactions on Information and Systems, v.E91-D n.2, p.170-177, February 2008
	Esther M. Arkin , Sándor P. Fekete , Kamrul Islam , Henk Meijer , Joseph S. B. Mitchell , Yurai Núòez-Rodríguez , Valentin Polishchuk , David Rappaport , Henry Xiao, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Computational Geometry: Theory and Applications, v.42 n.6-7, p.582-605, August, 2009