Complexity of Hamiltonian cycle reconfiguration

DOI10.3390/a11090140zbMath1461.68166OpenAlexW2890221297WikidataQ129251238 ScholiaQ129251238MaRDI QIDQ2633261

Asahi Takaoka

Publication date: 8 May 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a11090140

zbMATH Keywords

Hamiltonian cyclesplit graphsPSPACE-completeunit interval graphschordal bipartite graphsstrongly chordal graphscombinatorial reconfigurationbipartite permutation graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (8)

1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids ⋮ The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs ⋮ Editorial: Special issue on reconfiguration problems ⋮ Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs ⋮ Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of dominating set reconfiguration
• On the complexity of reconfiguration problems
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• A linear time recognition algorithm for proper interval graphs
• Characterizations of strongly chordal graphs
• Bipartite permutation graphs
• Proper interval graphs and the guard problem
• Efficient graph representations
• HAMILTONian circuits in chordal bipartite graphs
• Optimal greedy algorithms for indifference graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• The Complexity of (List) Edge-Coloring Reconfiguration Problem
• Graph Classes: A Survey
• On the Switch Markov Chain for Perfect Matchings
• Statistical problems involving permutations with restricted positions

This page was built for publication: Complexity of Hamiltonian cycle reconfiguration