On the complexity of optimal matching reconfiguration

DOI10.1007/978-3-030-10801-4_18zbMath1444.68142OpenAlexW2909128280MaRDI QIDQ2206232

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 theorymatchingsNP-hardnessreconfiguration

Mathematics Subject Classification ID

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

Related Items (3)

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Unnamed Item

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