Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation

Uproszczony widok
dc.abstract.enThe notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm. In recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., 2O(t)) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., 2O(t log t)) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problems, namely, HAMILTONIAN CYCLE.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorZiobro, Michał
dc.contributor.authorPilipczuk, Marcin
dc.date.accessioned2024-01-25T00:40:50Z
dc.date.available2024-01-25T00:40:50Z
dc.date.issued2019
dc.description.financeNie dotyczy
dc.description.volume24
dc.identifier.doi10.1145/3368631
dc.identifier.issn1084-6654
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/107156
dc.identifier.weblinkhttps://dl.acm.org/doi/pdf/10.1145/3368631
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofJournal of Experimental Algorithmics
dc.relation.pages1-18
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleFinding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation
dc.typeJournalArticle
dspace.entity.typePublication