Solving Hamiltonian cycle by an EPT algorithm for a non-sparse parameter

DOI10.1016/j.dam.2016.02.008zbMath1365.05165arXiv1411.5849OpenAlexW1506206384MaRDI QIDQ2357164

Sigve Hortemo Sæther

Publication date: 19 June 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

EPTHamiltonian cycleparameterized complexitysplit-matching-width

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• A simplified NP-complete satisfiability problem
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Parameterized Algorithms for Modular-Width
• Between Treewidth and Clique-Width
• Intractability of Clique-Width Parameterizations
• Edge Dominating Sets in Graphs
• Decomposition of Directed Graphs
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Unnamed Item
• Unnamed Item
• Unnamed Item