File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Approximating the longest cycle problem on graphs with bounded degree

TitleApproximating the longest cycle problem on graphs with bounded degree
Authors
Issue Date2005
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science, 2005, v. 3595, p. 870-884 How to Cite?
AbstractIn 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4 then G contains a cycle of length Ω(n logd-12), and showed that this bound is best possible if true. In this paper we present an O(n 3) algorithm for finding a cycle of length Ω(n logb2) in G, where b = max{64, 4d + 1}. Our result substantially improves the best existing bound Ω(n log2(d-1)2+12). © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/158860
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChen, Gen_US
dc.contributor.authorGao, Zen_US
dc.contributor.authorYu, Xen_US
dc.contributor.authorZang, Wen_US
dc.date.accessioned2012-08-08T09:03:58Z-
dc.date.available2012-08-08T09:03:58Z-
dc.date.issued2005en_US
dc.identifier.citationLecture Notes In Computer Science, 2005, v. 3595, p. 870-884en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/158860-
dc.description.abstractIn 1993, Jackson and Wormald conjectured that if G is a 3-connected n-vertex graph with maximum degree d ≥ 4 then G contains a cycle of length Ω(n logd-12), and showed that this bound is best possible if true. In this paper we present an O(n 3) algorithm for finding a cycle of length Ω(n logb2) in G, where b = max{64, 4d + 1}. Our result substantially improves the best existing bound Ω(n log2(d-1)2+12). © Springer-Verlag Berlin Heidelberg 2005.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.titleApproximating the longest cycle problem on graphs with bounded degreeen_US
dc.typeConference_Paperen_US
dc.identifier.emailZang, W:wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-26844454502en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-26844454502&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume3595en_US
dc.identifier.spage870en_US
dc.identifier.epage884en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridChen, G=7406541233en_US
dc.identifier.scopusauthoridGao, Z=7402833246en_US
dc.identifier.scopusauthoridYu, X=7404115058en_US
dc.identifier.scopusauthoridZang, W=7005740804en_US
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats