Title :
A Matching Based Automata for Distributed Graph Algorithms
Author :
Daigle, J. Paul ; Prasad, Sushil K.
Author_Institution :
Dept. of Comput. Sci., Georgia State Univ., Atlanta, GA, USA
Abstract :
A consistent problem with distributed algorithms for graph problems is scalability. Here we present a scalable automata that can easily be modified to solve a number of problems. We focus on the Minimum Weighted Vertex Cover problem, showing that our approach improves on the best known algorithm, reducing the number of communication rounds from O(log n) to O(log Δ). We then show how our framework can be modified to solve for Edge Coloring and Independent Set.
Keywords :
automata theory; distributed algorithms; graph theory; pattern matching; set theory; communication rounds; distributed graph algorithm; edge coloring; independent set; matching based automata; minimum weighted vertex cover problem; scalable automata; Approximation algorithms; Approximation methods; Automata; Color; Distributed algorithms; Equations; Maintenance engineering;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.198
