Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
DOI10.1137/20M1364370zbMath1487.05207OpenAlexW2955954498MaRDI QIDQ5074950
Takehiro Ito, Naoyuki Kamiyama, Yoshio Okamoto, Naonori Kakimura, Yusuke Kobayashi
Publication date: 10 May 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1364370
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Cites Work
- Unnamed Item
- Finding shortest paths between graph colourings
- Complexity of independent set reconfigurability problems
- A counterexample to the Hirsch conjecture
- Pancake flipping is hard
- On the complexity of reconfiguration problems
- Complexity of token swapping and its variants
- Flip distance between triangulations of a simple polygon is NP-complete
- Flip distance between two triangulations of a point set is NP-complete
- Adjacency of the 0-1 knapsack problem
- The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
- Adjacency on the constrained assignment problem
- On the complexity of computing the diameter of a polytope
- On certain polytopes associated with graphs
- Swapping colored tokens on graphs
- The Hirsch conjecture is true for (0,1)-polytopes
- A combinatorial study of partial order 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
- Swapping labeled tokens on graphs
- Reconfiguration of maximum-weight \(b\)-matchings in a graph
- Flip distance between triangulations of a planar point set is APX-hard
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- The complexity of change
- Degree-Constrained Subgraph Reconfiguration is in P
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The adjacency relation on the traveling salesman polytope is NP-Complete
- Sequentially Swapping Colored Tokens on Graphs
- The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
- The Perfect Matching Reconfiguration Problem
- Finding Short Paths on Polytopes by the Shadow Vertex Algorithm
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- Flip distances between graph orientations
This page was built for publication: Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
