dc.contributor.author | Fomin, Fedor | |
dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Sagunov, Danil | |
dc.contributor.author | Simonov, Kirill | |
dc.date.accessioned | 2023-01-10T13:02:06Z | |
dc.date.available | 2023-01-10T13:02:06Z | |
dc.date.created | 2022-11-04T12:25:39Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3042360 | |
dc.description.abstract | In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2^𝒪(k)⋅n^𝒪(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl – Leibniz Center for Informatics | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Longest Cycle Above Erdös-Gallai Bound | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2022 the authors | en_US |
dc.source.articlenumber | 55 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | https://doi.org/10.4230/LIPIcs.ESA.2022.55 | |
dc.identifier.cristin | 2069160 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 55:1-55:15 | en_US |
dc.relation.project | Norges forskningsråd: 314528 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2022, 244, 55:1-55:15. | en_US |
dc.source.volume | 244 | en_US |