Using local adaptations to reconfigure a spanning tree of a network

We define the notion of a local adaptation of a spanning tree in a biconnected graph, and consider the number of local adaptations required to reconfigure the spanning tree. We show that ⌈ n 2 ⌉ ⌈ n 2 − 1⌉/2 local adaptations are sufficient, and may be necessary, to make a node a leaf in the spannin...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1995-02, Vol.57 (1), p.67-74
Main Author: Pruhs, Kirk R.
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematics
Sciences and techniques of general use
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We define the notion of a local adaptation of a spanning tree in a biconnected graph, and consider the number of local adaptations required to reconfigure the spanning tree. We show that ⌈ n 2 ⌉ ⌈ n 2 − 1⌉/2 local adaptations are sufficient, and may be necessary, to make a node a leaf in the spanning tree, that n 2 8 + o(n 2) local adaptations are sufficient, and may be necessary, to add or delete an edge from the spanning tree, and that 3n 2 4 + o(n 2) local adaptations are sufficient to transform one spanning tree to another spanning tree.
ISSN:0166-218X
1872-6771
DOI:10.1016/0166-218X(94)00077-Q