|
Published Articles >> Table of Contents >> Abstract
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7
p. 174a
Fault Tolerant Algorithms for Orderings and Colorings
Wayne Goddard, Clemson University
Stephen T. Hedetniemi, Clemson University
David P. Jacobs, Clemson University
Pradip K. Srimani, Clemson University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2004.1303177
Send link to a friend
| Abstract |
|
A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. [2] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. There is a strong connection between k-forward numberings and colorings of graphs. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata [9], as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.
|
 Additional Information
|
Citation:
Wayne Goddard, Stephen T. Hedetniemi, David P. Jacobs, Pradip K. Srimani,
"Fault Tolerant Algorithms for Orderings and Colorings,"
ipdps,
p. 174a,
18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 7,
2004
|
|
