File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximating Longest Cycles in Graphs with Bounded Degrees

TitleApproximating Longest Cycles in Graphs with Bounded Degrees
Authors
Chen, GTGao, ZCYu, XXZang, WA
Keywordsbounded degree
3-connected components
long cycles
algorithm
Issue Date2006
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php
Citation
SIAM Journal on Computing, 2006, v. 36 n. 3, p. 635-656 How to Cite?
DOI: http://dx.doi.org/10.1137/050633263
AbstractJackson and Wormald conjecture that if $G$ is a 3-connected $n$-vertex graph with maximum degree $d\ge 4$, then $G$ has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.
Persistent Identifierhttp://hdl.handle.net/10722/44905
ISSN
0097-5397
2023 Impact Factor: 1.2
2023 SCImago Journal Rankings: 2.143
ISI Accession Number ID
WOS:000243279700004

 

DC FieldValueLanguage
dc.contributor.authorChen, GTen_HK
dc.contributor.authorGao, ZCen_HK
dc.contributor.authorYu, XXen_HK
dc.contributor.authorZang, WAen_HK
dc.date.accessioned2007-10-30T06:13:06Z-
dc.date.available2007-10-30T06:13:06Z-
dc.date.issued2006en_HK
dc.identifier.citationSIAM Journal on Computing, 2006, v. 36 n. 3, p. 635-656en_HK
dc.identifier.issn0097-5397en_HK
dc.identifier.urihttp://hdl.handle.net/10722/44905-
dc.description.abstractJackson and Wormald conjecture that if $G$ is a 3-connected $n$-vertex graph with maximum degree $d\ge 4$, then $G$ has a cycle of length $\Omega(n^{\log_{d-1}2})$. We show that this conjecture holds when $d-1$ is replaced by $\max\{64,4d+1\}$. Our proof implies a cubic algorithm for finding such a cycle.en_HK
dc.format.extent290984 bytes-
dc.format.extent30898 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/pdf-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sicomp.php-
dc.relation.ispartofSIAM Journal on Computing-
dc.rights© 2006 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Computing in volume 36, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectbounded degreeen_HK
dc.subject3-connected componentsen_HK
dc.subjectlong cyclesen_HK
dc.subjectalgorithmen_HK
dc.titleApproximating Longest Cycles in Graphs with Bounded Degreesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0097-5397&volume=36&issue=3&spage=635&epage=656&date=2006&atitle=Approximating+Longest+Cycles+in+Graphs+with+Bounded+Degreesen_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1137/050633263en_HK
dc.identifier.scopuseid_2-s2.0-34250810881-
dc.identifier.hkuros125053-
dc.identifier.volume36-
dc.identifier.issue3-
dc.identifier.spage635-
dc.identifier.epage656-
dc.identifier.isiWOS:000243279700004-
dc.identifier.issnl0097-5397-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats