Complexity of Hamiltonian cycle reconfiguration

DOI10.3390/A11090140MaRDI QIDQ2633261zbMATH OpenOpenAlexWikidataFDO

Authors Asahi Takaoka

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Hamiltonian cyclesplit graphschordal bipartite graphsstrongly chordal graphsunit interval graphsPSPACE-completecombinatorial reconfigurationbipartite permutation graphs

Mathematics Subject Classification ID

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

Recommendations

• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• Shortest reconfiguration of perfect matchings via alternating cycles
• The complexity of independent set reconfiguration on bipartite graphs
• scientific article; zbMATH DE number 1308950
• HAMILTONian circuits in chordal bipartite graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear time recognition algorithm for proper interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Bipartite permutation graphs
• Characterizations of strongly chordal graphs
• Efficient graph representations
• Games, puzzles, and computation
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• On the complexity of reconfiguration problems
• On the switch Markov chain for perfect matchings
• Optimal greedy algorithms for indifference graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Proper interval graphs and the guard problem
• Statistical problems involving permutations with restricted positions
• The complexity of (list) edge-coloring reconfiguration problem
• The complexity of change
• The complexity of dominating set reconfiguration
• The complexity of independent set reconfiguration on bipartite graphs

Cited in

(16)

• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids
• Complexity of the hamiltonian cycle in regular graph problem
• Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
• Shortest reconfiguration of perfect matchings via alternating cycles
• Reconfiguration of spanning trees with degree constraints or diameter constraints
• The Hamiltonian path graph is connected for simple \(s,t\) paths in rectangular grid graphs
• scientific article; zbMATH DE number 1249657 (Why is no real title available?)
• Hamiltonian circuits with generalised cost
• Editorial: Special issue on reconfiguration problems
• 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
• Hamiltonian cycle reconfiguration with answer set programming
• Recongo: bounded combinatorial reconfiguration with answer set programming

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

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