The first fully polynomial stabilizing algorithm for BFS tree construction

DOI10.1016/J.IC.2019.01.005MaRDI QIDQ2272977zbMATH OpenOpenAlexWikidataFDO

Authors Alain Cournier, Vincent Villain, Stephane Rovedakis

Publication date 17 September 2019

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2019.01.005

zbMATH Keywords

distributed systemsfault tolerancespanning tree

Mathematics Subject Classification ID

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

Recommendations

• The first fully polynomial stabilizing algorithm for BFS tree construction
• A new polynomial silent stabilizing spanning-tree construction algorithm
• Space efficient and time optimal distributed BFS tree construction
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph
• Time Optimal Asynchronous Self-stabilizing Spanning Tree

Cites work

• scientific article; zbMATH DE number 4209563 (Why is no real title available?)
• A Snap-Stabilizing DFS with a Lower Space Requirement
• A new polynomial silent stabilizing spanning-tree construction algorithm
• A self-stabilizing algorithm for constructing breadth-first trees
• A self-stabilizing algorithm for constructing spanning trees
• An O(n)-time self-stabilizing leader election algorithm
• Distributed network protocols
• Introduction to Distributed Algorithms
• Low communication self-stabilization through randomization
• Parallel Processing and Applied Mathematics
• Self-stabilization
• Self-stabilization with path algebra
• Self-stabilizing depth-first search
• Self-stabilizing leader election in optimal space under an arbitrary scheduler
• Self-stabilizing leader election in polynomial steps
• Self-stabilizing systems in spite of distributed control
• The diameter of a scale-free random graph
• The first fully polynomial stabilizing algorithm for BFS tree construction
• Time Optimal Asynchronous Self-stabilizing Spanning Tree
• Time optimal self-stabilizing synchronization

Cited in

(6)

• Asynchronous self-stabilization made fast, simple, and energy-efficient
• Space efficient and time optimal distributed BFS tree construction
• The first fully polynomial stabilizing algorithm for BFS tree construction
• A new polynomial silent stabilizing spanning-tree construction algorithm
• Communication efficient self-stabilizing leader election
• Analysis of a memory-efficient self-stabilizing BFS spanning tree construction

This page was built for publication: The first fully polynomial stabilizing algorithm for BFS tree construction

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