Reconfiguration of Spanning Trees with Many or Few Leaves

DOI10.4230/LIPIcs.ESA.2020.24OpenAlexW3082258454MaRDI QIDQ5874492

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

Publication date: 7 February 2023

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

zbMATH Keywords

polynomial-time algorithmsPSPACEspanning treescombinatorial reconfiguration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (6)

Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ Feedback vertex set reconfiguration in planar graphs ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Brief announcement: Distributed reconfiguration of spanning trees ⋮ How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks ⋮ Reconfiguration of time-respecting arborescences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of dominating set reconfiguration
• On the complexity of reconfiguration problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Reconfiguration in bounded bandwidth and tree-depth
• Token sliding on chordal graphs
• The coloring reconfiguration problem on specific graph classes
• Shortest reconfiguration of matchings
• Introduction to reconfiguration
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
• Reconfiguring spanning and induced subgraphs

This page was built for publication: Reconfiguration of Spanning Trees with Many or Few Leaves