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-10T12:11:59Z | |
dc.date.available | 2023-01-10T12:11:59Z | |
dc.date.created | 2022-11-04T16:17:56Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3042300 | |
dc.description.abstract | We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k. | 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 | Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms | 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 | 1 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | https://doi.org/10.4230/LIPIcs.MFCS.2022.1 | |
dc.identifier.cristin | 2069410 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 1:1-1:4 | en_US |
dc.relation.project | Norges forskningsråd: 314528 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2022, 241, 1:1-1:4. | en_US |
dc.source.volume | 241 | en_US |