Open AccessA Distributed Election and Spanning Tree Algorithm Based on Depth First Search
Author(s) -
Sven Skyum
Publication year - 1987
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v16i232.7588
Subject(s) - tree traversal , graph traversal , depth first search , spanning tree , breadth first search , computer science , modular design , tree (set theory) , distributed minimum spanning tree , graph , algorithm , connection (principal bundle) , minimum spanning tree , theoretical computer science , search algorithm , mathematics , discrete mathematics , combinatorics , geometry , operating system
The existence of an effective traversal algorithm for a class of graphs has proven useful in connection with election problems for those classes. In this paper we show how a general traversal algorithm, such as depth first search, can be turned into an effective election algorithm using modular techniques. The presented method also constructs a spanning tree for the graph.