The first fully polynomial stabilizing algorithm for BFS tree construction

DOI10.1016/J.IC.2019.01.005zbMATH Open1439.68028OpenAlexW2913859261WikidataQ128486239 ScholiaQ128486239MaRDI QIDQ2272977FDOQ2272977

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

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

zbMATH Keywords

distributed systemsfault tolerancespanning tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• 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)