File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Approximating the longest cycle problem on graphs with bounded degree
| Title | Approximating the longest cycle problem on graphs with bounded degree |
|---|---|
| Authors | |
| Issue Date | 2005 |
| Publisher | Springer 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? |
| Abstract | In 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 Identifier | http://hdl.handle.net/10722/158860 |
| ISSN | 2020 SCImago Journal Rankings: 0.249 |
| References |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Chen, G | en_US |
| dc.contributor.author | Gao, Z | en_US |
| dc.contributor.author | Yu, X | en_US |
| dc.contributor.author | Zang, W | en_US |
| dc.date.accessioned | 2012-08-08T09:03:58Z | - |
| dc.date.available | 2012-08-08T09:03:58Z | - |
| dc.date.issued | 2005 | en_US |
| dc.identifier.citation | Lecture Notes In Computer Science, 2005, v. 3595, p. 870-884 | en_US |
| dc.identifier.issn | 0302-9743 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/158860 | - |
| dc.description.abstract | In 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.language | eng | en_US |
| dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_US |
| dc.relation.ispartof | Lecture Notes in Computer Science | en_US |
| dc.title | Approximating the longest cycle problem on graphs with bounded degree | en_US |
| dc.type | Conference_Paper | en_US |
| dc.identifier.email | Zang, W:wzang@maths.hku.hk | en_US |
| dc.identifier.authority | Zang, W=rp00839 | en_US |
| dc.description.nature | link_to_subscribed_fulltext | en_US |
| dc.identifier.scopus | eid_2-s2.0-26844454502 | en_US |
| dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-26844454502&selection=ref&src=s&origin=recordpage | en_US |
| dc.identifier.volume | 3595 | en_US |
| dc.identifier.spage | 870 | en_US |
| dc.identifier.epage | 884 | en_US |
| dc.publisher.place | Germany | en_US |
| dc.identifier.scopusauthorid | Chen, G=7406541233 | en_US |
| dc.identifier.scopusauthorid | Gao, Z=7402833246 | en_US |
| dc.identifier.scopusauthorid | Yu, X=7404115058 | en_US |
| dc.identifier.scopusauthorid | Zang, W=7005740804 | en_US |
| dc.identifier.issnl | 0302-9743 | - |