Shortest reconfiguration of matchings

DOI10.1007/978-3-030-30786-8_13MaRDI QIDQ2301540zbMATH OpenOpenAlexFDO

Authors Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler

Publication date 24 February 2020

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

zbMATH Keywords

approximation hardnessfixed-parameter tractabilitymatchingsreconfiguration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the complexity of optimal matching reconfiguration
• Shortest reconfiguration of perfect matchings via alternating cycles
• Shortest reconfiguration of perfect matchings via alternating cycles
• Approximation and hardness of token swapping
• The Perfect Matching Reconfiguration Problem

Cited in

(13)

• On the complexity of optimal matching reconfiguration
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar
• Shortest reconfiguration of perfect matchings via alternating cycles
• Linear transformations between colorings in chordal graphs
• Shortest reconfiguration of perfect matchings via alternating cycles
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Feedback vertex set reconfiguration in planar graphs
• Inapproximability of shortest paths on perfect matching polytopes
• Reconfiguring planar perfect matchings via bounded length alternating cycles
• Gap preserving reductions between reconfiguration problems
• Inapproximability of shortest paths on perfect matching polytopes
• A generalized matching reconfiguration problem
• Independent set reconfiguration on directed graphs

This page was built for publication: Shortest reconfiguration of matchings

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