Reconfiguration of Spanning Trees with Many or Few Leaves

DOI10.4230/LIPICS.ESA.2020.24OpenAlexW3082258454MaRDI QIDQ5874492FDOQ5874492

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

Publication date 7 February 2023

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

zbMATH Keywords

spanning treespolynomial-time algorithmsPSPACEcombinatorial reconfiguration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A survey on the use of Markov chains to randomly sample colourings
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
• Shortest reconfiguration of matchings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The coloring reconfiguration problem on specific graph classes
• The complexity of change
• The complexity of dominating set reconfiguration
• Token sliding on chordal graphs
• Token sliding on split graphs

Cited in

(6)

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

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

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