On the complexity of optimal matching reconfiguration

DOI10.1007/978-3-030-10801-4_18MaRDI QIDQ2206232zbMATH OpenOpenAlexFDO

Authors Manoj Gupta, Hitesh Kumar, Neeldhara Misra

Publication date 22 October 2020

Full work available at URL https://doi.org/10.1007/978-3-030-10801-4_18

zbMATH Keywords

graph theoryNP-hardnessmatchingsreconfiguration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the Complexity of Reconfiguration Problems
• On the complexity of reconfiguration problems
• The Perfect Matching Reconfiguration Problem
• Shortest reconfiguration of matchings
• scientific article; zbMATH DE number 2145225
• scientific article; zbMATH DE number 123780
• scientific article; zbMATH DE number 3921983
• Complexity of matching problems

Cited in

(7)

• Reconfiguration of maximum weight \(b\)-matchings in a graph
• Optimal reconfiguration of optimal ladder lotteries
• Shortest reconfiguration of perfect matchings via alternating cycles
• Inapproximability of shortest paths on perfect matching polytopes
• Reconfiguration of maximum-weight b-matchings in a graph
• scientific article; zbMATH DE number 7525498 (Why is no real title available?)
• The Perfect Matching Reconfiguration Problem

This page was built for publication: On the complexity of optimal matching reconfiguration

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