An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width

DOI10.1007/s00453-019-00663-9zbMath1433.68279arXiv1702.06095OpenAlexW2995628723MaRDI QIDQ5918121

O-joung Kwon, Benjamin Bergougnoux, Mamadou Moustapha Kanté

Publication date: 14 April 2020

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Hamiltonian cycleclique-widthexponential time hypothesisEulerian trailedge dominating setsXP-algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Unnamed Item ⋮ Unnamed Item ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Digraphs of Bounded Width ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Monadic second-order evaluations on tree-decomposable graphs
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Eulerian graphs and related topics. Part 1, Volume 1
• A partial k-arboretum of graphs with bounded treewidth
• Edge dominating set and colorings on graphs with fixed clique-width
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• Intractability of Clique-Width Parameterizations
• Easy problems for tree-decomposable graphs
• Clique-Width is NP-Complete
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Clique-width III
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Finding Branch-Decompositions and Rank-Decompositions
• An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width