The Perfect Matching Reconfiguration Problem
From MaRDI portal
Publication:5092444
DOI10.4230/LIPIcs.MFCS.2019.80OpenAlexW2970799922MaRDI QIDQ5092444
Marc Heinrich, Arnaud Mary, Marthe Bonamy, Takehiro Ito, Moritz Mühlenthaler, Yusuke Kobayashi, Kunihiro Wasa, Nicolas Bousquet
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.06184
Related Items (6)
TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ On reachable assignments under dichotomous preferences ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ On the longest flip sequence to untangle segments in the plane ⋮ Complexity results on untangling red-blue matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- Linear-time algorithm for sliding tokens on trees
- On the complexity of reconfiguration problems
- Flip distance between triangulations of a simple polygon is NP-complete
- Flip distance between two triangulations of a point set is NP-complete
- Token jumping in minor-closed classes
- Reconfiguration in bounded bandwidth and tree-depth
- Flipping edges in triangulations
- Spaces of domino tilings
- Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
- On counting perfect matchings in general graphs
- Introduction to reconfiguration
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Graphs of triangulations and perfect matchings
- Independent Set Reconfiguration in Cographs and their Generalizations
- The complexity of change
- Reconfiguring Independent Sets in Claw-Free Graphs
- On the Switch Markov Chain for Perfect Matchings
- Switching Distance Between Graphs with the Same Degrees
- Counting Perfect Matchings and the Switch Chain
- Parameterized Complexity of Graph Constraint Logic
- Statistical problems involving permutations with restricted positions
- On the Parameterized Complexity for Token Jumping on Graphs
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness
- Partitions and Their Representative Graphs
This page was built for publication: The Perfect Matching Reconfiguration Problem
