Using local adaptations to reconfigure a spanning tree of a network

DOI10.1016/0166-218X(94)00077-QMaRDI QIDQ1345965zbMATH OpenWikidataFDO

Authors Kirk Pruhs

Publication date 11 June 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00077-Q

zbMATH Keywords

biconnected graphboundextremal problemsleafleaf problemlocal adaptationlocal changenetworkspanning tree

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Applications of graph theory (05C90)

Review text

Let \(G\) be a biconnected graph, let \(S\) be a spanning tree in \(G\), and let \(v\) be a leaf in \(G\), i.e. \(\deg v=1\). A local adaptation \((v, w, x)\) is the event of \(v\) consisting of deleting the link \(vw\) from \(S\) and adding the link \(vx\) to \(S\). Let \(u\) be a vertex in \(G\). The leaf problem is to find a sequence of local adaptations that makes \(u\) a leaf in the spanning tree. It is proved that \(\lceil n/2 \rceil \cdot \lceil n/2-1 \rceil/2\) local adaptions are sufficient to solve any instance of the leaf problem. It is also shown that this bound is tight.

Recommendations

• Brief announcement: Distributed reconfiguration of spanning trees
• scientific article; zbMATH DE number 1156650
• The complexity of the locally connected spanning tree problem
• An efficient distributed algorithm for centering a spanning tree of a biconnected graph

Cited in

(2)

• scientific article; zbMATH DE number 1156650 (Why is no real title available?)
• Brief announcement: Distributed reconfiguration of spanning trees

This page was built for publication: Using local adaptations to reconfigure a spanning tree of a network

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