scientific article; zbMATH DE number 7525498

DOI10.4230/LIPIcs.ESA.2019.61MaRDI QIDQ5075806

Yusuke Kobayashi, Yoshio Okamoto, Naoyuki Kamiyama, Takehiro Ito, Naonori Kakimura

Publication date: 11 May 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

matchingcombinatorial reconfigurationalternating cyclescombinatorial shortest paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Complexity of independent set reconfigurability problems
• A counterexample to the Hirsch conjecture
• On the complexity of reconfiguration problems
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• On certain polytopes associated with graphs
• The Hirsch conjecture is true for (0,1)-polytopes
• On the complexity of optimal matching reconfiguration
• Shortest reconfiguration of matchings
• An asymptotically improved upper bound on the diameter of polyhedra
• Introduction to reconfiguration
• The complexity of change
• The Planar Hamiltonian Circuit Problem is NP-Complete