Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation

DOI10.4230/LIPICS.SEA.2018.29MaRDI QIDQ5140740zbMATH OpenOpenAlexFDO

Authors Michal Ziobro, Marcin Pilipczuk

Publication date 16 December 2020

Full work available at URL https://arxiv.org/abs/1803.00927

zbMATH Keywords

empirical evaluation of algorithmsHamiltonian cycletree-width

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: The 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 the 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., $2^{O(t)}$) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., $2^{O(tlogt)}$) 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 problem, namely Hamiltonian Cycle.

Recommendations

• Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• On Exact Algorithms for Treewidth
• On exact algorithms for treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth

Cites work

• A Dynamic Programming Approach to Sequencing Problems
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Engineering Motif Search for Large Graphs
• Fast exact algorithms for Hamiltonicity in claw-free graphs
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• Matching is as easy as matrix inversion
• Parameterized algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
• Trimmed Moebius inversion and graphs of bounded degree
• Turbocharging treewidth heuristics

Cited in

(2)

• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation

This page was built for publication: Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140740)