Complexity of Hamiltonian cycle reconfiguration

DOI10.3390/A11090140zbMATH Open1461.68166OpenAlexW2890221297WikidataQ129251238 ScholiaQ129251238MaRDI QIDQ2633261FDOQ2633261

Authors: 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

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

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)

Cites Work

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

Cited In (15)

• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids
• Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
• Complexity of the hamiltonian cycle in regular graph problem
• 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
• Title not available (Why is that?)
• Hamiltonian circuits with generalised cost
• 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
• 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)