Reconfiguration of spanning trees with degree constraints or diameter constraints

DOI10.1007/s00453-023-01117-zarXiv2201.04354OpenAlexW4363647757MaRDI QIDQ6053473

Haruka Mizuta, Paul Ouvrard, Kunihiro Wasa, Takehiro Ito, Yusuke Kobayashi, Akira Suzuki, Nicolas Bousquet

Publication date: 27 September 2023

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

polynomial-time algorithmsPSPACEspanning treescombinatorial reconfiguration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Feedback vertex set reconfiguration in planar graphs

Cites Work

• On the complexity of reconfiguration problems
• On the minimum diameter spanning tree problem
• Bounded degree spanning trees (extended abstract)
• Maintaining spanning trees of small diameter
• Minimum restricted diameter spanning trees.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
• Introduction to reconfiguration
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Complexity of Hamiltonian cycle reconfiguration
• Multiple-Source Shortest Paths in Embedded Graphs
• The complexity of change
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Reducibility among Combinatorial Problems
• Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
• Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Reconfiguration of spanning trees with degree constraints or diameter constraints