Shortest reconfiguration of matchings

DOI10.1007/978-3-030-30786-8_13OpenAlexW2976085618MaRDI QIDQ2301540FDOQ2301540

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

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

zbMATH Keywords

fixed-parameter tractabilitymatchingsreconfigurationapproximation hardness

Mathematics Subject Classification ID

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

Cited In (8)

• Feedback vertex set reconfiguration in planar graphs
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Shortest reconfiguration of perfect matchings via alternating cycles
• On the complexity of optimal matching reconfiguration
• Title not available (Why is that?)
• Inapproximability of shortest paths on perfect matching polytopes
• Title not available (Why is that?)
• 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)