Brief announcement: Distributed reconfiguration of spanning trees

DOI10.1007/978-3-031-21017-4_25MaRDI QIDQ6097213zbMATH OpenFDO

Authors

Publication date 12 June 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distributed algorithmsreconfigurationspanning trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Abstract: In a reconfiguration problem, given a problem and two feasible solutions of the problem, the task is to find a sequence of transformations to reach from one solution to the other such that every intermediate state is also a feasible solution to the problem. In this paper, we study the distributed spanning tree reconfiguration problem and we define a new reconfiguration step, called $k$-simultaneous add and delete, in which every node is allowed to add at most $k$ edges and delete at most $k$ edges such that multiple nodes do not add or delete the same edge. We first observe that, if the two input spanning trees are rooted, then we can do the reconfiguration using a single $1$-simultaneous add and delete step in one round in the CONGEST model. Therefore, we focus our attention towards unrooted spanning trees and show that transforming an unrooted spanning tree into another using a single $1$-simultaneous add and delete step requires $Omega(n)$ rounds in the LOCAL model. We additionally show that transforming an unrooted spanning tree into another using a single $2$-simultaneous add and delete step can be done in $O(logn)$ rounds in the CONGEST model.

Recommendations

• Using local adaptations to reconfigure a spanning tree of a network
• Reconfiguration of Steiner trees in an unweighted graph
• Distributed reconfiguration of maximal independent sets
• Reconfiguring (non-spanning) arborescences
• Distributed algorithms for low stretch spanning trees

Cites work

• Distributed Computing: A Locality-Sensitive Approach
• Distributed recoloring
• Distributed reconfiguration of maximal independent sets
• Locality in Distributed Graph Algorithms
• On the complexity of reconfiguration problems
• Reconfiguration of Spanning Trees with Many or Few Leaves
• Reconfiguring directed trees in a digraph

Cited in

(4)

• Using local adaptations to reconfigure a spanning tree of a network
• Distributed computation and reconfiguration in actively dynamic networks
• Distributed Tree Rearrangements for Reachability and Robust Connectivity
• Short and local transformations between ( +1)-colorings

This page was built for publication: Brief announcement: Distributed reconfiguration of spanning trees

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