A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs

Journal of Parallel and Distributed Computing - Tập 70 - Trang 406-415 - 2010
Nabil Guellati1, Hamamache Kheddouci2
1Department of Computer Science, University of Abderrahmane Mira, Bejaia, Algeria
2LIESP Laboratory, University of Claude Bernard, Lyon, France

Tài liệu tham khảo

Bruell, 1999, Self-stabilizing algorithms for finding centers and medians of trees, SIAM Journal on Computing, 29, 600, 10.1137/S0097539798427156

S. Cantarell, A.K. Datta, F. Petit, Self-stabilizing atomicity refinement allowing neighborhood concurrency, in: Proc. 6th International Symposium on Self-Stabilizing Systems, 2003, pp. 102–112

S. Chattopadhyay, L. Higham, K. Seyffarth, Dynamic and self-stabilizing distributed matching, in: Proc. 21st ACM Symposium on Principles of Distributed Computing, 2002, pp. 290–297

P. Chaudhuri, H. Thompson, A self-stabilizing algorithm for L(2,1)-labeling trees, in: Proc. IASTED International Conference on Parallel and Distributed Computing and Networks, 2005, pp. 627–632

Datta, 2009, A self-stabilizing O(k)-time k-clustering algorithm, Computer Journal

L. Dekar, H. Kheddouci, Distance-2 self-stabilizing algorithm for a b-coloring of graphs, in: Proc. 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2008, pp. 19–31

Diestel, 2005

Dijkstra, 1974, Self-stabilizing systems in spite of distributed control, Communication of the ACM, 17, 643, 10.1145/361179.361202

Dolev, 2000

Dolev, 1997, Self-stabilizing routing and related protocols, Journal of Parallel and Distributed Computing, 42, 122, 10.1006/jpdc.1997.1317

Dolev, 1997, Superstabilizing protocols for dynamic distributed systems, Chicago Journal of Theoretical Computer Science, 1997

Dolev, 1997, Resource bounds for self-stabilizing message-driven protocols, SIAM Journal on Computing, 26, 273, 10.1137/S0097539792235074

Dolev, 1993, Self stabilization of dynamic systems assuming only read/write atomicity, Distributed Computing, 7, 3, 10.1007/BF02278851

Dolev, 2009, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Theoretical Computer Science, 410, 514, 10.1016/j.tcs.2008.10.006

F.C. Gartner, A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms, Swiss Federal Institute of Technology Tech. Rep. IC/2003/38, School of Computer and Communication Sciences, Lausanne, Switzerland, 2003

Gavoille, 2009, On the complexity of distributed graph coloring with local minimality constraints, Networks, 54, 12, 10.1002/net.20293

S. Ghosh, A. Gupta, T. Herman, S.V. Pemmaraju, Fault-containing self-stabilizing algorithms, in: Proc. 15th ACM Symposium on Principles of Distributed Computing, 1996

Ghosh, 1993, A self-stabilizing algorithm for coloring planar graphs, Distributed Computing, 7, 55, 10.1007/BF02278856

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, A robust distributed generalized matching protocol that stabilizes in linear time, in: Proc. 23rd International Conference on Distributed Computing Systems Workshops, 2003, pp. 461–465

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph, in: Proc. 17th International Parallel and Distributed Processing Symposium, 2003

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Self-stabilizing distributed algorithm for strong matching in a system graph, in: Proc. 10th International Conference on High Performance Computing, 2003

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks, in: Proc. International Parallel and Distributed Processing Symposium, 2003

W. Goddard, S.T. Hedetniemi, D.P. Jacobs, P.K. Srimani, Fault tolerant algorithms for orderings and colorings, in: Proc. 18th International Parallel and Distributed Processing Symposium, 2004, pp. 174–182

Goddard, 2008, Self-stabilizing graph protocols, Parallel Processing Letters, 18, 189, 10.1142/S0129626408003314

W. Goddard, S.T. Hedetniemi, Z. Shi, An anonymous self-stabilizing algorithm for 1-maximal matching in trees, in: Proc. International Conference on Parallel and Distributed Processing Techniques and Applications, 2006, pp. 797–803

M. Gradinariu, S. Tixeuil, Self-stabilizing vertex coloration and arbitrary graphs, in: Proc. 4th International Conference on Principles of Distributed Systems, 2000, pp. 55–70

Haynes, 1998

Hedetniemi, 2003, Self-stabilizing algorithms for minimal dominating sets and maximal independent sets, Computer Mathematics and Applications, 46, 805, 10.1016/S0898-1221(03)90143-X

Hedetniemi, 2001, Maximal matching stabilizes in time O(m), Information Processing Letters, 80, 221, 10.1016/S0020-0190(01)00171-5

Hedetniemi, 2003, Linear time self-stabilizing colorings, Information Processing Letters, 87, 251, 10.1016/S0020-0190(03)00299-0

Herman, 2002, Self-stabilization bibliography: Access guide, Working Paper WP-1, Chicago Journal of Theoretical Computer Science

Hsu, 1992, A self-stabilizing algorithm for maximal matching, Information Processing Letters, 43, 77, 10.1016/0020-0190(92)90015-N

Huang, 2005, Self-stabilizing coloration in anonymous planar networks, Information Processing Letter, 95, 307, 10.1016/j.ipl.2005.03.005

S.T. Huang, C.H. Tzeng, Distributed edge coloration for bipartite networks, in: Proc. 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS’06, 2006, pp. 363–377

S.T. Huang, Y.H. Wang, Self-stabilizing acyclic coloring of graphs, in: Proc. IASTED International Conference on Parallel and Distributed Computing and Networks, 2004

Huang, 2008, A linear-time self-stabilizing algorithm for the minimal 2-dominating set problem in general networks, Journal of Information Science and Engineering, 24, 175

Huang, 2007, A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model, Computers & Mathematics with Applications, 54, 350, 10.1016/j.camwa.2007.01.021

M. Ikeda, S. Kamei, H. Kakugawa, A space-optimal self-stabilizing algorithm for the maximal independent set problem, in: Proc. 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies, 2002

A. Jain, A. Gupta, A distributed self-stabilizing algorithm for finding a connected dominating set in a graph, in: Proc. 6th International Conference on Parallel and Distributed Computing Applications and Technologies, 2005, pp. 615–619

H. Kakugawa, T. Masuzawa, A self-stabilizing minimal dominating set algorithm with safe convergence, in: Proc. 20th International Parallel and Distributed Processing Symposium, 2006

S. Kamei, H. Kakugawa, A self-stabilizing algorithm for the distributed minimal k-redundant dominating set problem in tree network, in: Proc. 4th International Conference on Parallel and Distributed Computing, Applications and Technologies, 2003

Kamei, 2005, A self-stabilizing approximation algorithm for the distributed minimum k-domination, IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E88-A, 1109, 10.1093/ietfec/e88-a.5.1109

S. Kamei, H. Kakugawa, A self-stabilizing distributed approximation algorithm for the minimum connected dominating set, in: Proc. 21st International Parallel and Distributed Processing Symposium, 2007, pp. 1–8

Karaata, 2001, Self-stabilizing strong fairness under weak fairness, IEEE Transactions on Parallel and Distributed Systems, 12, 337, 10.1109/71.920585

Karaata, 2000, A distributed self-stabilizing algorithm for finding maximum matching, Computer Systems Science and Engineering, 15, 175

A. Kosowski, L. Kuszner, Self-stabilizing algorithms for graph coloring with improved performance guarantees, in: Proc. 8th International Conference on Artificial Intelligence and Soft Computing, 2006, pp. 1150–1159

J. Kratochvil, Z. Tuza, M. Voigt, On the b-chromatic number of graphs, in: Proc. 28th International on Graph-Theoretic Concepts in Computer Science, 2002, pp. 310–320

F. Kuhn, T. Moscibroda, R. Wattenhofer, What cannot be computed locally! in: Proc. 23rd Annual ACM Symposium on Principles of Distributed Computing, 2004, pp. 300–309

Lin, 2003, An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set, IEEE Transactions on Parallel and Distributed Systems, 14, 742, 10.1109/TPDS.2003.1225054

Lin, 2008, A self-stabilizing algorithm for finding a minimal distance-2 dominating set in distributed systems, Journal of Information Science and Engineering, 24, 1709

Linial, 1992, Locality in distributed graph algorithms, SIAM Journal on Computing, 21, 193, 10.1137/0221015

F. Manne, M. Mjelde, A self-stabilizing weighted matching algorithm, in: Proc. 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2007, pp. 383–393

F. Manne, M. Mjelde, L. Pilard, S. Tixeuil, A new self-stabilizing maximal matching algorithm, in: Proc. 14th International Colloquium on Structural Information and Communication Complexity, 2007, pp. 96–108

F. Manne, M. Mjelde, L. Pilard, S. Tixeuil, A self-stabilizing 2/3-approximation algorithm for the maximum matching problem, in: Proc. 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2008

T. Masuzawa, S. Tixeuil, A self-stabilizing link coloring algorithm resilient to unbounded byzantine faults in arbitrary networks, in: Proc. 9th International Conference on Principles of Distributed Systems, December 2005

Nesterenko, 2002, Stabilization-preserving atomicity refinement, Journal of Parallel and Distributed Computing, 62, 766, 10.1006/jpdc.2001.1828

M. Nesterenko, A. Arora, Tolerance to unbounded byzantine faults, in: Proc. 21st IEEE Symposium on Reliable Distributed Systems, 2002

Y. Sakurai, F. Ooshita, T. Masuzawa, A self-stabilizing link-coloring protocol resilient to byzantine faults in tree networks, in: Proc. 8th International Conference on Principles of Distributed Systems, 2004

Schneider, 1993, Self-stabilization, ACM Computing Surveys, 25, 45, 10.1145/151254.151256

Shi, 2004, An anonymous self-stabilizing algorithm for 1-maximal independent set in trees, Information Processing Letters, 91, 77, 10.1016/j.ipl.2004.03.010

S.K. Shukla, D.J. Rosenkrantz, S.S. Ravi, Developing self-stabilizing coloring algorithms via systematic randomization, in: Proc. 1st International Workshop on Parallel Processing, 1994, pp. 668–673

S.K. Shukla, D.J. Rosenkrantz, S.S. Ravi, Observations on self-stabilizing graph algorithms for anonymous networks, in: Proc. 2nd Workshop on Self-Stabilizing Systems, 1995

P.K. Srimani, Z. Xu, Self-stabilizing algorithms of constructing spanning tree and weakly connected minimal dominating set, in: Proc. 27th International Conference on Distributed Computing Systems Workshops, 2007

H. Sun, B. Effantin, H. Kheddouci, A self-stabilizing algorithm for the minimum color sum of a graph, in: Proc. 9th International Conference on Distributed Computing and Networking, 2008, pp. 209–214

Sur, 1993, A self-stabilizing algorithm for coloring bipartite graphs, Information Sciences, 69, 219, 10.1016/0020-0255(93)90121-2

Tel, 1994, Maximal matching stabilizes in quadratic time, Information Processing Letters, 49, 271, 10.1016/0020-0190(94)90098-1

Turau, 2007, Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler, Information Processing Letters, 103, 88, 10.1016/j.ipl.2007.02.013

Tzeng, 2007, A self-stabilizing (Δ+4)-edge-coloring algorithm for planar graphs in anonymous uniform systems, Information Processing Letters, 101, 168, 10.1016/j.ipl.2006.09.004

Z. Xu, S.T. Hedetniemi, W. Goddard, P.K. Srimani, A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph, in: Proc. 5th International Workshop on Distributed Computing, 2003

Thông tin
Thông tin xuất bản

Journal of Parallel and Distributed Computing

Tập 70

406-415

Thông tin tác giả