Degree-Constrained Subgraph Reconfiguration is in P

DOI10.1007/978-3-662-48054-0_42zbMath1465.68108arXiv1508.01372OpenAlexW2964160072MaRDI QIDQ2946420

Moritz Mühlenthaler

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Reconfiguration of regular induced subgraphs ⋮ Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Reconfiguring (non-spanning) arborescences ⋮ Unnamed Item ⋮ Reconfiguring directed trees in a digraph ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguring spanning and induced subgraphs ⋮ Introduction to reconfiguration

Cites Work

• The complexity of rerouting shortest paths
• On the complexity of reconfiguration problems
• Another look at the degree constrained subgraph problem
• The complexity of change
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings

This page was built for publication: Degree-Constrained Subgraph Reconfiguration is in P