Reconfiguration of Minimum Steiner Trees via Vertex Exchanges

DOI10.4230/LIPICS.MFCS.2019.79MaRDI QIDQ5092443zbMATH OpenOpenAlexFDO

Authors Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/lipics.mfcs.2019.79

zbMATH Keywords

combinatorial reconfigurationgraph algorithmsSteiner tree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Reconfiguration of Steiner trees in an unweighted graph
• Reconfiguration of vertex-disjoint shortest paths on graphs
• Reoptimization of Steiner Trees
• Shortest paths between shortest paths
• Simple and fast reoptimizations for the Steiner tree problem

Cites work

• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Graph Classes: A Survey
• 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
• Rerouting shortest paths in planar graphs
• Shortest paths between shortest paths
• The complexity of change
• The complexity of rerouting shortest paths

Cited in

(3)

• Reconfiguration of Spanning Trees with Many or Few Leaves
• Reconfiguration of spanning trees with degree constraints or diameter constraints
• Reconfiguration of vertex-disjoint shortest paths on graphs

This page was built for publication: Reconfiguration of Minimum Steiner Trees via Vertex Exchanges

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