DocumentCode
3143573
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
fYear
2011
fDate
16-20 May 2011
Firstpage
632
Lastpage
638
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location
Shanghai
ISSN
1530-2075
Print_ISBN
978-1-61284-425-1
Electronic_ISBN
1530-2075
Type
conf
DOI
10.1109/IPDPS.2011.198
Filename
6008886
Link To Document