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

fixed-parameter tractabilitymatchingsreconfigurationapproximation hardness

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

(8)

• Feedback vertex set reconfiguration in planar graphs
• Shortest reconfiguration of perfect matchings via alternating cycles
• Reconfiguration of Spanning Trees with Many or Few Leaves
• On the complexity of optimal matching reconfiguration
• scientific article; zbMATH DE number 7525461 (Why is no real title available?)
• Inapproximability of shortest paths on perfect matching polytopes
• scientific article; zbMATH DE number 7525498 (Why is no real title available?)
• Shortest Reconfiguration of Sliding Tokens on a Caterpillar

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)