臺灣博碩士論文加值系統

圖論的控制集問題的研究始於1960年代。一個分散式系統(例如：一個隨意網路)可以用一個無向簡單圖G=(V,E)來表示，其中V表示點集，而E表示點跟點之間的聯結關係。圖G的點集V的子集合D被稱為是控制集，若此子集D具有性質：V中的任一元素v屬於D或與D中的元素相鄰。如果一個控制集不真包含另一控制集，則稱其為極小控制集(簡記為MDS)。極小控制集在無線網路中的應用之一是使所需的資源中心保持為較少數目。
自我穩定是一個可用於設計分散式系統容忍暫時性錯誤的一個概念，並且是在1974年由Dijkstra提出。一個分散式系統是自我穩定的，如果它滿足：不論初始組態為何，系統總是能保證在有限時間內達到一個合法的(正確的)組態。此處所稱的系統組態是由系統中所有節點的狀態所組成。一個自我穩定演算法由一些規則所組成，每個規則都有其觸發條件及其對應動作，該動作能通過更新節點的變數來改變節點的狀態。每執行一個規則稱為是一步。本論文所提出的演算法的效能皆是以執行總步數來計算。自我穩定演算法有許多不同的執行模式，且執行模式是以排程器的概念來呈現。排程器分為公平的及不公平的兩種。眾所皆知，不公平的分散式排程器比其他類型的排程器更貼近實際使用狀況。
令n表示給定的分散式系統的節點數。在2007年，Turau對於MDS問題，提出了不公平的分散式排程器下的第一個線性時間的自我穩定演算法，此演算法在最多9n步之後穩定。在2008年，Goddard等人改進了上述演算法並做到最多5n步。我們將在本論文中提出一個採用不公平分散式排程器下最多4n步的自我穩定MDS演算法。
理想中，MDS演算法是希望能做到MDS-靜止的，亦即，若分散式系統的初始組態已經是一個MDS，則演算法將不執行任何動作。值得注意的是，在正常模式中，一個節點只能取得其一步內鄰居的資訊，我們稱這些資訊為1步資訊。不幸的是，在本論文中，我們將證明：1步資訊不足以建立一個MDS-靜止的演算法。在本論文中，我們將討論此一問題，並針對自我穩定MDS演算法提出一個新的性能評量，稱為穩定性。我們推廣這部份的結果至其他自我穩定演算法，並將自我穩定演算法分類為四個層次。特別的是，我們將證明：在2步資訊模式下，可建構出自我穩定MDS-靜止的演算法，且其穩定時間之上界為2n步。
在2005年，Xu提出了圖的帶正負號星控制集的概念，在2007年，Wang給出了完全圖的帶正負號控制數，詳細定義請參見本論文的第五章。在2010年，Atapour等人定義了帶正負號星控制劃分數，並利用完全圖具有可完全1-因子分解或可完全漢米爾頓圈分解的性質，計算出完全圖的帶正負號星控制劃分數。在2012年，我與印度學者Chelvam等人合作，定義了有向圖的帶正負號星控制數，給出了全部有向凱式圖的帶正負號星控制數，與無向凱式圖的帶正負號星控制數的部份結果，並推廣這些結果至可完全{2,1}-因子分解的正則圖。

The study of the domination problem in graph theory began in the nineteen-sixties. A distributed system such as an ad hoc network can be modeled by an undirected simple graph G = (V;E), where V represents the set of nodes (i.e., processes) and E represents the set of interconnections between processes of the distributed system. A subset D of the vertex set V of G is a dominating set if each vertex v in V is either a member of D or adjacent to a vertex in D. A dominating set of G is a minimal dominating set (MDS) if none of its proper subsets is a dominating set of G. An MDS
has an application of clustering in wireless networks and is maintained for minimizing the number of required resource centers.
Self-stabilization is a concept of designing a distributed system for transient fault toleration and was introduced by Dijkstra in 1974. A distributed system is self-stabilizing if, regardless of its initial configuration, the system is guaranteed to reach a legitimate (i.e., correct) configuration in a finite time. Here the system configuration consists of the state of every process. A self-stabilizing algorithm comprises a collection of rules and each rule has a trigger precondition and an action. The action changes the state of the node by updating its variables. An execution of a rule is called a move. The performance of the proposed algorithms of this thesis is measured by the total number of moves executed by an algorithm. Various execution models have been used in self-stabilizing algorithms and these are encapsulated with the
notion of daemons. A daemon can be fair or unfair. It is well-known that an unfair distributed daemon is more practical than other types of daemons.
Let n denote the number of nodes (processes) in a given distributed system. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the MDS problem under an unfair distributed daemon; this algorithm stabilizes in at most 9n moves. In 2008, Goddard et al. improved the result to a 5n-move algorithm. It is interesting to develop an algorithm that takes less moves than the best known result—5n moves using an unfair distributed daemon. In this thesis, we will present a 4n-move self-stabilizing MDS algorithm using an unfair distributed daemon.
It is desired that an MDS algorithm is MDS-silent, which means that if the original configuration of the distributed system is already an MDS, then the algorithm should not make any move. Note that in the normal model, a node can only access the information of its 1-hop neighbors and we call such information distance-1 information. Unfortunately, in this thesis we will prove that distance-1 information is not sufficient for building up an MDS-silent algorithm for a distributed system. In this thesis, we will discuss this problem and propose a new performance measure, called stableness, for self-stabilizing MDS algorithms. We also generalize this result to categorize all self-stabilizing algorithms into four levels. In particular, we will show that a self-stabilizing MDS-silent algorithm can be built up under the distance-2 model and the stabilizing time is upper bounded by 2n.
Let G be a simple connected graph with vertex set V (G) and edge set E(G). A function f : E(G)→{-1,1} is called a signed star dominating function (SSDF) on G if Σ_{e in E}(v) f(e) >=1 for every v in V(G), where E(v) is the set of all edges incident to v. The signed star domination number of G is defined as SS(G) = min weight sum of f which is an SSDF on G. Let Ω be a symmetric generating subset of nonidentity elements of Γ. The Cayley graph Cay(Γ; Ω) corresponding to Γ and Ω is the ordinary graph with vertex set Γ and edge set E. In this thesis, we obtain exact values for the signed star domination number of all Cayley digraphs CayD(Γ; S) and certain classes of Cayley graphs Cay(Γ; Ω), which is later
generalized to f2; 1g-factorable graphs. Note that these solutions are from a joint work with Chelvam and Kalaimurugan.

Introduction......................... 1
Self-stabilization................... 8
Self-stabilizing MDS algorithm....... 16
The stableness of MDS algorithms..... 31
The distance-2 model................. 48
The signed star domination........... 55
Conclusions.......................... 67

@book{HHS98,
title={Fundamentals of Domination in Graphs},
author = {Teresa W. Haynes and Stephen T. Hedetniemi and Peter J. Slater},
isbn={9780824700331},
lccn={97043490},
series={Monographs and Textbooks in Pure and Applied Mathematics},
year={1998},
publisher={CRC Press}
}

@book{Dol00,
author = {Shlomi Dolev},
title = {Self-stabilization},
publisher = {MIT Press},
year = {2000},
}

@book{DBW00,
title={Introduction to Graph Theory},
author={Douglas B. West},
edition={2nd},
isbn={9780130144003},
year={2000},
publisher={Prentice-Hall, Inc.}
}

@article{Dij74,
author = {Edsger W. Dijkstra},
title = {Self-stabilizing Systems in Spite of Distributed Control},
journal = {Communications of the ACM},
issue_date = {Nov. 1974},
volume = {17},
number = {11},
month = nov,
year = {1974},
issn = {0001-0782},
pages = {643--644},
numpages = {2},
url = {http://doi.acm.org/10.1145/361179.361202},
doi = {10.1145/361179.361202},
acmid = {361202},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {distributed control, error recovery, harmonious cooperation, multiprocessing, mutual exclusion, networks, robustness, self-repair, self-stabilization, sharing, synchronization}
}

@article{AWF03,
author = {Khaled M. Alzoubi and Peng-Jun Wan and Ophir Frieder},
title = {Maximal independent set, weakly-connected dominating set, and induced spanners in wireless ad hoc networks},
journal = {International Journal of Foundations of Computer Science},
volume = 14,
number = 2,
year = 2003,
pages = {287--303}
} %??

@inproceedings{GHJ03D,
author = {Goddard, Wayne and Hedetniemi, Stephen T. and Jacobs, David P. and Srimani, Pradip K.},
title = {A Self-Stabilizing Distributed Algorithm for Minimal Total Domination in an Arbitrary System Graph},
booktitle = {Proceedings of the 8th International Symposium on Parallel and Distributed Processing},
series = {IPDPS'03},
year = {2003},
isbn = {0-7695-1926-1},
pages = {240--243},
url = {http://dl.acm.org/citation.cfm?id=838237.838664},
acmid = {838664},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

@article{GHJ05,
author = {Goddard, Wayne and Hedetniemi, Stephen T. and Jacobs, David P. and Srimani, Pradip K.},
title = {Self-stabilizing global optimization algorithms for large network graphs},
journal = {International Journal of Distributed Sensor Networks},
volume = 1,
number = {3--4},
year = 2010,
pages = {329--344}
}

@INPROCEEDINGS{GHJ03I,
author = {Wayne Goddard and Stephen T. Hedetniemi David P. Jacobs and Pradip K Srimani},
title = {Self-Stabilizing Protocols for Maximal Matching and Maximal Independent Sets for Ad Hoc Networks},
booktitle = {Proceedings of the 5th IPDPS Workshop on Advances in Parallel and Distributed Computational Models},
series = {WAPDCM'03},
year = {2003},
pages = {162--167},
publisher = {IEEE Computer Society}
}

@inproceedings{GS10,
author = {Wayne Goddard and Pradip K. Srimani},
booktitle = {Proceedings of the 1st International Multi-Conference on Complexity, Informatics, and Cybernetics},
series = {IMCIC'10},
title = {Anonymous self-stabilizing distributed algorithms for connected dominating set in a network graph},
year = {2010},
}

@inproceedings{XHG03,
author = {Zhenyu Xu and Stephen T. Hedetniemi and Wayne Goddard and Pradip K. Srimani},
booktitle = {Proceedings of the 5th International Workshop on Distributed Computing, Springer LNCS 2918},
series = {IWDC'03},
title = {A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph},
year = {2003},
pages = {26--32}
}

@article{HHJ03,
author = {Sandra M. Hedetniemi and Stephen T. Hedetniemi and David P. Jacobs and Pradip K. Srimani},
title = {Self-stabilizing algorithms for minimal dominating sets and maximal independent sets},
journal = {Computer Mathematics and Applications},
volume = 46,
number = {5--6},
year = 2003,
pages = {805--811}
}

@article{SGH04,
author = {Zhengnan Shi and Wayne Goddard and Stephen T. Hedetniemi},
title = {An anonymous self-stabilizing algorithm for $1$-maximal independent set in trees},
journal = {Information Processing Letters},
volume = 91,
number = 2,
year = 2004,
pages = {77--83}
}

@Article{BYK14,
title = {Efficient self-stabilizing algorithms for minimal total $k$-dominating sets in graphs},
author = {Yacine Belhoul and Said Yahiaoui and Hamamache Kheddouci},
year = {2014},
month = jun,
journal = {Information Processing Letters},
volume = {114},
number = {7},
pages = {339--343},
publisher = {Elsevier},
language = {en},
url = {http://liris.cnrs.fr/publis/?id=6464}
}

@article{GGH04,
author = {Martin Gairing and Wayne Goddard and Stephen T. Hedetniemi and Petter Kristiansen and Alice A. McRae},
title = {Distance-two information in self-stabilizing algorithms},
journal = {Parallel Processing Letters},
volume = {14},
number = {3--4},
pages = {387--398},
year = {2004},
doi = {10.1142/S0129626404001970},
URL = {http://www.worldscientific.com/doi/abs/10.1142/S0129626404001970},
eprint = {http://www.worldscientific.com/doi/pdf/10.1142/S0129626404001970}
}

@inproceedings{KM06,
author = {Kakugawa, Hirotsugu and Masuzawa, Toshimitsu},
title = {A self-stabilizing Minimal Dominating Set Algorithm with Safe Convergence},
booktitle = {Proceedings of the 20th International Conference on Parallel and Distributed Processing},
series = {IPDPS'06},
year = {2006},
location = {Rhodes Island, Greece},
pages = {263--263},
numpages = {1},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

@article{Tur07,
author = {Volker Turau},
title = {Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler},
journal = {Information Processing Letters},
volume = {103},
number = {3},
pages = {88--93},
year = {2007},
issn = {0020-0190},
doi = {http://dx.doi.org/10.1016/j.ipl.2007.02.013},
url = {http://www.sciencedirect.com/science/article/pii/S0020019007000488}
}

@article{GHJ08,
author = {Wayne Goddard and Stephen T. Hedetniemi and David P. Jacobs and Pradip K. Srimani and Zhenyu Xu},
title = {Self-stabilizing graph protocols},
journal = {Parallel Processing Letters},
volume = 18,
number = 1,
year = 2008,
pages = {189--199}
}

@incollection {DK08,
author = {Lyes Dekar and Hamamache Kheddouci},
title = {Distance-$2$ Self-stabilizing Algorithm for a b-Coloring of Graphs},
booktitle = {Stabilization, Safety, and Security of Distributed Systems},
series = {Lecture Notes in Computer Science},
editor = {Kulkarni, Sandeep and Schiper, Andr\'e},
publisher = {Springer Berlin / Heidelberg},
pages = {19--31},
volume = {5340},
year = {2008}
}

@article{GHJ08k,
author = {Wayne Goddard and Stephen T. Hedetniemi and David P. Jacobs and Vilmar Trevisan},
title = {Distance-$k$ knowledge in self-stabilizing algorithms},
journal = {Theoretical Computer Science},
volume = 399,
number = {1--2},
year = 2008,
pages = {118--127}
}

@article{GK10,
author = {Nabil Guellati and Hamamache Kheddouci},
title = {A survey on self-stabilizing algorithms for independent, domination, coloring, and matching in graphs},
journal = {Journal of Parallel and Distributed Computing},
volume = 70,
number = 4,
year = 2010,
pages = {406--415}
}


@article{Tur12,
author = {Volker Turau},
title = {Efficient transformation of distance-$2$ self-stabilizing algorithms},
journal = {Journal of Parallel Distribted Computing},
volume = 72,
number = 4,
year = 2012,
pages = {603--612}
}

@incollection{WC13,
author={Well Y. Chiu and Chiuyuan Chen},
year={2013},
isbn={978-3-642-45277-2},
booktitle={Combinatorial Algorithms},
volume={8288},
series={Lecture Notes in Computer Science},
doi={10.1007/978-3-642-45278-9_11},
title={Linear-time Self-stabilizing Algorithms for Minimal Domination in Graphs},
url={http://dx.doi.org/10.1007/978-3-642-45278-9_11},
publisher={Springer Berlin Heidelberg},
pages={115--126}
}

@article{WCT14,
author = {Well Y. Chiu and Chiuyuan Chen and Shih-Yu Tsai},
title = {A $4n$-move self-stabilizing algorithm for the minimal dominating set problem using an unfair distributed daemon},
journal = {Information Processing Letters},
volume = 114,
number = 10,
year = 2014,
pages = {515--518},
issn = {0020-0190},
doi = {http://dx.doi.org/10.1016/j.ipl.2014.04.011},
url = {http://www.sciencedirect.com/science/article/pii/S0020019014000702}
}

@article{ASG10,
author = {M. Atapour and S. M. Sheikholeslami and A.N. Ghameshlou and L. Volkmann},
title = {Signed star domatic number of a graph},
journal = {Discrete Applied Mathematics},
volume = {158},
number = {3},
pages = {213--218},
year = {2010},
issn = {0166-218X},
doi = {http://dx.doi.org/10.1016/j.dam.2009.09.015},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X09003680}
}

@article{Jah09,
author = {S. Jahanbekam},
title = {A comment to: Two classes of edge domination in graphs},
journal = {Discrete Applied Mathematics},
volume = {157},
number = {2},
pages = {400--401},
year = {2009},
issn = {0166-218X},
doi = {http://dx.doi.org/10.1016/j.dam.2008.06.016},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X08002771}
}

@article{SS08,
author = {R. Saei and S.M. Sheikholeslami},
title = {Signed star $k$-subdomination numbers in graphs},
journal = {Discrete Applied Mathematics},
volume = 156,
number = 15,
pages = {3066--3070},
year = {2008},
issn = {0166-218X},
doi = {http://dx.doi.org/10.1016/j.dam.2008.01.020},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X08000425}
}

@article{Wan07,
author = {Changping Wang},
title = {The signed star domination numbers of the Cartesian product graphs},
journal = {Discrete Applied Mathematics},
volume = {155},
number = {11},
pages = {1497--1505},
year = {2007},
issn = {0166-218X},
doi = {http://dx.doi.org/10.1016/j.dam.2007.04.008},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X07001060}
}

@article{Xu01,
author = {Baogen Xu},
title = {On signed edge domination numbers of graphs},
journal = {Discrete Mathematics},
volume = 239,
number = {1--3},
pages = {179--189},
year = 2001,
issn = {0012-365X},
doi = {http://dx.doi.org/10.1016/S0012-365X(01)00044-9},
url = {http://www.sciencedirect.com/science/article/pii/S0012365X01000449}
}

@article{Xu05,
author = {Baogen Xu},
title = {On edge domination numbers of graphs},
journal = {Discrete Mathematics},
volume = 294,
number = 3,
pages = {311--316},
year = 2005,
issn = {0012-365X},
doi = {http://dx.doi.org/10.1016/j.disc.2004.11.008},
url = {http://www.sciencedirect.com/science/article/pii/S0012365X05000890}
}

@article{Xu06,
author = {Baogen Xu},
title = {Two classes of edge domination in graphs},
journal = {Discrete Applied Mathematics},
volume = 154,
number = 10,
pages = {1541--1546},
year = 2006,
issn = {0166-218X},
doi = {http://dx.doi.org/10.1016/j.dam.2005.12.007},
url = {http://www.sciencedirect.com/science/article/pii/S0166218X06000126}
}

@article{CKW12,
author = {Thirugnanam Tamizh Chelvam and G. Kalaimurugan and Well Y. Chou},
title = {The sighed star domination number of {C}ayley graphs},
journal = {Discrete Mathematics, Algorithms and Applications},
volume = {04},
number = {02},
pages = {1250017},
year = {2012},
issn = {1793-8309},
doi = {10.1142/S1793830912500176},
URL = {http://www.worldscientific.com/doi/abs/10.1142/S1793830912500176},
eprint = {http://www.worldscientific.com/doi/pdf/10.1142/S1793830912500176}
}

@article{Sch93,
author = {Marco Schneider},
title = {Self-stabilization},
journal = {ACM Computing Surveys},
volume = {25},
number = {1},
pages = {45--67},
year = {1993}
}

@article{DIM93,
year={1993},
issn={0178-2770},
journal={Distributed Computing},
volume={7},
number={1},
doi={10.1007/BF02278851},
title = {Self-stabilization of Dynamic Systems Assuming Only Read/Write Atomicity},
url={http://dx.doi.org/10.1007/BF02278851},
publisher={Springer-Verlag},
author={Dolev, Shlomi and Israeli, Amos and Moran, Shlomo},
pages={3--16},
language={English},
issue_date = {November 1993},
month = nov,
numpages = {14},
acmid = {1081400},
address = {London, UK, UK},
keywords = {protocol combination, read/write atomicity, self-stabilization},
}


@INPROCEEDINGS{SRR95,
author = {Sandeep K. Shukla and Daniel J. Rosenkrantz and S. S. Ravi},
title = {Observations on self-stabilizing graph algorithms for anonymous networks},
booktitle = {Proceedings of the 2nd Workshop on Self-Stabilizing Systems},
year = {1995},
series = {WSS'95},
pages = {7.1--7.15}
}

@INPROCEEDINGS{SRR97,
author = {Sandeep K. Shukla and Daniel J. Rosenkrantz and S. S. Ravi},
title = {Simulation and Validation Tool for Self-Stabilizing Protocols},
booktitle = {Proceedings of 2nd SPIN Workshop, Volume 32 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science},
numpages = {16},
year = {1997}
}

@ARTICLE{IR81,
author = {Alon Itai and Michael Rodeh},
title = {Symmetry Breaking In Distributed Networks},
journal = {Information and Computation},
year = {1981},
volume = {88},
pages = {150--158}
}


@INPROCEEDINGS{DH95,
author = {Shlomi Dolev and Ted Herman},
title = {SuperStabilizing Protocols for Dynamic Distributed Systems},
booktitle = {Proceedings of the 2nd Workshop on Self-Stabilizing Systems},
year = {1995},
series = {WSS'95},
pages = {3.1--3.15}
}

@article{BGK99,
author = {Bruell, Steven C. and Ghosh, Sukumar and Karaata, Mehmet Hakan and Pemmaraju, Sriram V.},
title = {Self-Stabilizing Algorithms for Finding Centers and Medians of Trees},
journal = {SIAM Journal on Computing},
issue_date = {Oct. 1999},
volume = {29},
number = {2},
month = oct,
year = {1999},
issn = {0097-5397},
pages = {600--614},
numpages = {15},
url = {http://dx.doi.org/10.1137/S0097539798427156},
doi = {10.1137/S0097539798427156},
acmid = {333129},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
keywords = {center, distributed algorithm, median, self-stabilization, tree}
}

@inproceedings{CHS02,
author = {Chattopadhyay, Subhendu and Higham, Lisa and Seyffarth, Karen},
title = {Dynamic and Self-stabilizing Distributed Matching},
booktitle = {Proceedings of the 21st Annual Symposium on Principles of Distributed Computing},
series = {PODC'02},
year = {2002},
isbn = {1-58113-485-1},
location = {Monterey, California},
pages = {290--297},
numpages = {8},
url = {http://doi.acm.org/10.1145/571825.571877},
doi = {10.1145/571825.571877},
acmid = {571877},
publisher = {ACM},
address = {New York, NY, USA},
}

@article{DLV10,
author = {Datta, Ajoy K. and Larmore, Lawrence L. and Vemula, Priyanka},
title = {A Self-Stabilizing {$O(k)$}-Time $k$-Clustering Algorithm},
journal = {The Computer Journal},
issue_date = {March 2010},
volume = {53},
number = {3},
month = mar,
year = {2010},
issn = {0010-4620},
pages = {342--350},
numpages = {9},
url = {http://dx.doi.org/10.1093/comjnl/bxn071},
doi = {10.1093/comjnl/bxn071},
acmid = {1742843},
publisher = {Oxford University Press},
address = {Oxford, UK},
}


@article{GKK09,
author = {Gavoille, Cyril and Klasing, Ralf and Kosowski, Adrian and Kuszner, Lukasz and Navarra, Alfredo},
title = {On the Complexity of Distributed Graph Coloring with Local Minimality Constraints},
journal = {Networks},
issue_date = {August 2009},
volume = {54},
number = {1},
month = aug,
year = {2009},
issn = {0028-3045},
pages = {12--19},
numpages = {8},
url = {http://dx.doi.org/10.1002/net.v54:1},
doi = {10.1002/net.v54:1},
acmid = {1572719},
publisher = {Wiley-Interscience},
address = {New York, NY, USA},
keywords = {distributed computing, graph coloring, greedy algorithm, randomization},
}

@inproceedings{GGH96,
author = {Ghosh, Sukumar and Gupta, Arobinda and Herman, Ted and Pemmaraju, Sriram V.},
title = {Fault-containing Self-stabilizing Algorithms},
booktitle = {Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing},
series = {PODC'96},
year = {1996},
isbn = {0-89791-800-2},
location = {Philadelphia, Pennsylvania, USA},
pages = {45--54},
numpages = {10},
url = {http://doi.acm.org/10.1145/248052.248057},
doi = {10.1145/248052.248057},
acmid = {248057},
publisher = {ACM},
address = {New York, NY, USA},
}

@article{GKH93,
author = {Ghosh, Sukumar and Karaata, Mehmet Hakan},
title = {A Self-stabilizing Algorithm for Coloring Planar Graphs},
journal = {Distributed Computing},
issue_date = {November 1993},
volume = {7},
number = {1},
month = nov,
year = {1993},
issn = {0178-2770},
pages = {55--59},
numpages = {5},
url = {http://dx.doi.org/10.1007/BF02278856},
doi = {10.1007/BF02278856},
acmid = {1081405},
publisher = {Springer-Verlag},
address = {London, UK},
keywords = {atomicity, directed acyclic graph, distributed algorithm, graph coloring, self-stabilization},
}

@inproceedings{GHJ03M,
author = {Goddard, Wayne and Hedetniemi, Stephen T. and Jacobs, David P. and Srimani, Pradip K.},
title = {A Robust Distributed Generalized Matching Protocol That Stabilizes in Linear Time},
booktitle = {Proceedings of the 23rd International Conference on Distributed Computing Systems},
series = {ICDCSW'03},
year = {2003},
isbn = {0-7695-1921-0},
pages = {461--465},
url = {http://dl.acm.org/citation.cfm?id=839280.840669},
acmid = {840669},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

@article{HJS02,
author = {Hedetniemi, Stephen T. and Jacobs, David P. and Srimani, Pradip K.},
title = {Maximal Matching Stabilizes in Time {$O(m)$}},
journal = {Information Processing Letters},
issue_date = {December 15, 2002},
volume = {80},
number = {5},
month = dec,
year = {2001},
issn = {0020-0190},
pages = {221--223},
numpages = {3},
url = {http://dx.doi.org/10.1016/S0020-0190(01)00171-5},
doi = {10.1016/S0020-0190(01)00171-5},
acmid = {513284},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
keywords = {analysis of algorithms, matching, self-stabilizing},
}


@article{HJS03,
author = {Hedetniemi, Stephen T. and Jacobs, David P. and Srimani, Pradip K.},
title = {Linear Time Self-stabilizing Colorings},
journal = {Information Processing Letters},
issue_date = {15 September 2003},
volume = {87},
number = {5},
month = sep,
year = {2003},
issn = {0020-0190},
pages = {251--255},
numpages = {5},
url = {http://dx.doi.org/10.1016/S0020-0190(03)00299-0},
doi = {10.1016/S0020-0190(03)00299-0},
acmid = {944098},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
keywords = {algorithms, distributed systems, grundy coloring, self-stabilizing coloring},
}

@article{HH92,
author = {Hsu, Su-Chu and Huang, Shing-Tsaan},
title = {A Self-stabilizing Algorithm for Maximal Matching},
journal = {Information Processing Letters},
issue_date = {Aug. 24, 1992},
volume = {43},
number = {2},
month = aug,
year = {1992},
issn = {0020-0190},
pages = {77--81},
numpages = {5},
url = {http://dx.doi.org/10.1016/0020-0190(92)90015-N},
doi = {10.1016/0020-0190(92)90015-N},
acmid = {139803},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
keywords = {distributed systems, fault-tolerance, maximal matching, self-stabilization, variant function},
}

@article{HHT05,
author = {Huang, Shing-Tsaan and Hung, Su-Shen and Tzeng, Chi-Hung},
title = {Self-stabilizing Coloration in Anonymous Planar Networks},
journal = {Information Processing Letters},
issue_date = {16 July 2005},
volume = {95},
number = {1},
month = jul,
year = {2005},
issn = {0020-0190},
pages = {307--312},
numpages = {6},
url = {http://dx.doi.org/10.1016/j.ipl.2005.03.005},
doi = {10.1016/j.ipl.2005.03.005},
acmid = {1710900},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
keywords = {Fault tolerance, Graph algorithms, Grundy coloring, Planar graph, Self-stabilization, Vertex coloring},
}

@inproceedings{HT06,
author = {Huang, Shing-Tsaan and Tzeng, Chi-Hung},
title = {Distributed Edge Coloration for Bipartite Networks},
booktitle = {Proceedings of the 8th International Conference on Stabilization, Safety, and Security of Distributed Systems},
series = {SSS'06},
year = {2006},
isbn = {978-3-540-49018-0},
location = {Dallas, TX, USA},
pages = {363--377},
numpages = {15},
url = {http://dl.acm.org/citation.cfm?id=1759076.1759104},
acmid = {1759104},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
keywords = {distributed system, edge coloring, fault-tolerance, selfstabilization},
}

@article{HCW08,
author = {Huang, Tetz C. and Chen, Chih-Yuan and Wang, Cheng-Pin},
title = {A Linear-Time Self-Stabilizing Algorithm for the Minimal $2$-Dominating Set Problem in General Networks},
journal = {Journal of Information Science and Engineering},
volume = {24},
number = {1},
year = {2008},
pages = {175--187},
numpages = {13}
}

@article{HLC07,
author = {Huang, Tetz C. and Lin, Ji-Cherng and Chen, Chih-Yuan and Wang, Cheng-Pin},
title = {A Self-stabilizing Algorithm for Finding a Minimal $2$-dominating Set Assuming the Distributed Demon Model},
journal = {Computers and Mathematics with Applications},
issue_date = {August, 2007},
volume = {54},
number = {3},
month = aug,
year = {2007},
issn = {0898-1221},
pages = {350--356},
numpages = {7},
url = {http://dx.doi.org/10.1016/j.camwa.2007.01.021},
doi = {10.1016/j.camwa.2007.01.021},
acmid = {1274514},
publisher = {Pergamon Press, Inc.},
address = {Tarrytown, NY, USA},
keywords = {Central demon model, Cut point, Distributed demon model, Minimal 2-dominating set, Self-stabilizing algorithm},
}

@article{MM75,
author = {A. Meir and J. W. Moon},
title = {Relations between packing and covering numbers of a tree},
journal = {Pacific Journal of Mathematics},
volume = {61},
number = {1},
year = {1975},
pages = {225--233},
}



@inproceedings{JG05,
author = {Jain, Ankur and Gupta, Arobinda},
title = {A Distributed Self-Stabilizing Algorithm for Finding a Connected Dominating Set in a Graph},
booktitle = {Proceedings of the 6th International Conference on Parallel and Distributed Computing Applications and Technologies},
series = {PDCAT'05},
year = {2005},
isbn = {0-7695-2405-2},
pages = {615--619},
numpages = {5},
url = {http://dx.doi.org/10.1109/PDCAT.2005.10},
doi = {10.1109/PDCAT.2005.10},
acmid = {1110362},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

@inproceedings{KK03,
author = {Kamei, Sayaka and Kakugawa, Hirotsugu},
title = {A self-stabilizing algorithm for the distributed minimal $k$-redundant dominating set problem in tree networks},
booktitle = {Proceedings of the 4th International Conference on Parallel and Distributed Computing, Applications and Technologies},
series = {PDCAT'03},
year = {2003},
pages = {720--724},
numpages = {5},
publisher = {IEEE},
address = {Washington, DC, USA},
}

@article{KK05,
author = {Kamei, Sayaka and Kakugawa, Hirotsugu},
title = {A Self-Stabilizing Approximation Algorithm for the Distributed Minimum $k$-Domination},
journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences},
issue_date = {May 2005},
volume = {E88-A},
number = {5},
month = may,
year = {2005},
issn = {0916-8508},
pages = {1109--1116},
numpages = {8},
url = {http://dx.doi.org/10.1093/ietfec/e88-a.5.1109},
doi = {10.1093/ietfec/e88-a.5.1109},
acmid = {1094738},
publisher = {Oxford University Press},
address = {Oxford, UK},
keywords = {self-stabilizing distributed algorithm, fault-tolerance, approximation, minimum k-dominating set, general networks},
}




@inproceedings{KK06,
author = {Kosowski, Adrian and Kuszner, Lukasz},
title = {Self-stabilizing Algorithms for Graph Coloring with Improved Performance Guarantees},
booktitle = {Proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing},
series = {ICAISC'06},
year = {2006},
isbn = {3-540-35748-3, 978-3-540-35748-3},
location = {Zakopane, Poland},
pages = {1150--1159},
numpages = {10},
url = {http://dx.doi.org/10.1007/11785231_120},
doi = {10.1007/11785231_120},
acmid = {2171728},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}

@inproceedings{KMW04,
author = {Kuhn, Fabian and Moscibroda, Thomas and Wattenhofer, Rogert},
title = {What Cannot Be Computed Locally!},
booktitle = {Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing},
series = {PODC'04},
year = {2004},
isbn = {1-58113-802-4},
location = {St. John's, Newfoundland, Canada},
pages = {300--309},
numpages = {10},
url = {http://doi.acm.org/10.1145/1011767.1011811},
doi = {10.1145/1011767.1011811},
acmid = {1011811},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {approximation hardness, distributed algorithms, dominating set, locality, lower bounds, maximal independent set, maximal matching, vertex cover},
}

@article{LH03,
author = {Lin, Ji-Cherng and Huang, Tetz C.},
title = {An Efficient Fault-Containing Self-Stabilizing Algorithm for Finding a Maximal Independent Set},
journal = {IEEE Transactions on Parallel and Distributed Systems},
issue_date = {August 2003},
volume = {14},
number = {8},
month = aug,
year = {2003},
issn = {1045-9219},
pages = {742--754},
numpages = {13},
url = {http://dx.doi.org/10.1109/TPDS.2003.1225054},
doi = {10.1109/TPDS.2003.1225054},
acmid = {940005},
publisher = {IEEE Press},
address = {Piscataway, NJ, USA},
keywords = {Central demon, maximal independent set, single transient fault, fault-containment, restrictions on guard conditions, primary variables, auxiliary secondary variables, stabilization time, contamination number.},
}


@article{Lin92,
author = {Linial, Nathan},
title = {Locality in Distributed Graph Algorithms},
journal = {SIAM Journal on Computing},
issue_date = {Feb. 1992},
volume = {21},
number = {1},
month = feb,
year = {1992},
issn = {0097-5397},
pages = {193--201},
numpages = {9},
url = {http://dx.doi.org/10.1137/0221015},
doi = {10.1137/0221015},
acmid = {130578},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
keywords = {distributed algorithms, graph theory, locality, lower bounds},
}

@inproceedings{MM07,
author = {Manne, Fredrik and Mjelde, Morten},
title = {A Self-stabilizing Weighted Matching Algorithm},
booktitle = {Proceedings of the 9th International Conference on Stabilization, Safety, and Security of Distributed Systems},
series = {SSS'07},
year = {2007},
isbn = {3-540-76626-X, 978-3-540-76626-1},
location = {Paris, France},
pages = {383--393},
numpages = {11},
url = {http://dl.acm.org/citation.cfm?id=1785110.1785139},
acmid = {1785139},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
keywords = {self-stabilizing algorithms, weighted matching},
}

@inproceedings{MMP07,
author = {Manne, Fredrik and Mjelde, Morten and Pilard, Laurence and Tixeuil, S{\'e}bastien},
title = {A New Self-stabilizing Maximal Matching Algorithm},
booktitle = {Proceedings of the 14th International Conference on Structural Information and Communication Complexity},
series = {SIROCCO'07},
year = {2007},
isbn = {978-3-540-72918-1},
location = {Castiglioncello, LI, Italy},
pages = {96--108},
numpages = {13},
url = {http://dl.acm.org/citation.cfm?id=1760631.1760643},
acmid = {1760643},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}

@incollection{MT05,
year={2006},
isbn={978-3-540-36321-7},
booktitle={Principles of Distributed Systems},
volume={3974},
series={Lecture Notes in Computer Science},
editor={Anderson, JamesH. and Prencipe, Giuseppe and Wattenhofer, Roger},
doi={10.1007/11795490_11},
title = {A Self-stabilizing Link-coloring Protocol Resilient to Unbounded {B}yzantine Faults in Arbitrary Networks},
url={http://dx.doi.org/10.1007/11795490_11},
publisher={Springer Berlin Heidelberg},
keywords={distributed protocol; self-stabilization; link-coloring; Byzantine fault; fault tolerance; fault containment},
author = {Masuzawa, Toshimitsu and Tixeuil, S{\'e}bastien},
pages={118--129},
language={English}
}

@TECHREPORT{Gar03,
author = {Felix C. Gartner},
title = {A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms},
institution = {Swiss Federal Institute of Technology Tech. Rep. IC/2003/38, School of Computer and Communication Sciences},
year = {2003},
ADDRESS = {Lausanne, Switzerland},
}

@article{PWC99,
author = {Reuay-Ching Pan and Jone-Zen Wang and Louis R. Chow},
title = {A Self-stabilizing Distributed Spanning Tree Construction Algorithm with a Distributed Demon},
journal = {Tamsui Oxford Journal of Mathematical Sciences},
issue_date = {May 2002},
volume = {15},
month = may, year = {1999},
pages = {23--32},
}

@incollection{LZ01,
author={Lisa Higham and Zhiying Liang},
month = oct,
year={2001},
volume={2180},
series={Lecture Notes in Computer Science},
title={Self-stabilizing minimum spanning tree construction on message-passing networks},
booktitle={Distributed Computing},
publisher={Springer-Verlag},
}

@incollection{CDP03,
year={2003},
isbn={978-3-540-40453-8},
booktitle={Self-Stabilizing Systems},
volume={2704},
series={Lecture Notes in Computer Science},
doi={10.1007/3-540-45032-7_8},
title={Self-Stabilizing Atomicity Refinement Allowing Neighborhood Concurrency},
url={http://dx.doi.org/10.1007/3-540-45032-7_8},
publisher={Springer Berlin Heidelberg},
author={Cantarell, S\'ebastien and Datta, AjoyK. and Petit, Franck},
pages={102--112},
language={English}
}

@mastersthesis{TC11,
author = {Shihyu Tsai},
title = {An efficient self-stabilizing algorithm for the minimal dominating set problem under a distributed scheduler},
school = {Department of Applied Mathematics, National Chiao Tung University, Hsinchu, Taiwan},
year = {2011},
}

@article{TH94,
author = {Ming-Shin Tsai and Shing-Tsaan Huang},
title = {A self-stabilizing algorithm for the shortest paths problem with a fully distributed demon},
journal = {Parallel Processing Letters},
volume = {4},
number = {1--2},
month = jun,
year = {1994},
pages = {65-72},
}

@incollection{BLB13,
year={1995},
isbn={978-3-540-60274-3},
booktitle={Distributed Algorithms},
volume={972},
series={Lecture Notes in Computer Science},
editor={H\'elary, Jean-Michel and Raynal, Michel},
doi={10.1007/BFb0022152},
title={A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm},
url={http://dx.doi.org/10.1007/BFb0022152},
publisher={Springer Berlin Heidelberg},
author={Butelle, Franck and Lavault, Christian and Bui, Marc},
pages={257--272},
language={English}
}


@INPROCEEDINGS{AS97,
author = {Gheorghe Antonoiu and Pradip K. Srimani},
title = {Distributed Self-Stabilizing Algorithm for Minimum Spanning Tree Construction},
booktitle = {European Conference on Parallel Processing},
year = {1997},
pages = {480--487},
publisher = {Springer-Verlag}
}

@ARTICLE{SSS92,
author = {Sumit Sur and Pradip K Srimani},
title = {A Self-Stabilizing Distributed Algorithm to Construct BFS Spanning Trees of a Symmetric Graph},
journal = {Computers and Mathematics with Applications},
year = {1992},
volume = {30}
}

@article{CYH91,
title = {A self-stabilizing algorithm for constructing spanning trees},
journal = {Information Processing Letters},
volume = {39},
number = {3},
pages = {147--151},
year = {1991},
doi = {http://dx.doi.org/10.1016/0020-0190(91)90111-T},
url = {http://www.sciencedirect.com/science/article/pii/002001909190111T},
author = {Nian-Shing Chen and Hwey-Pyng Yu and Shing-Tsaan Huang},
}




@inproceedings{SX07,
author = {Srimani, Pradip K. and Xu, Zhenyu},
title = {Self-Stabilizing Algorithms of Constructing Spanning Tree and Weakly Connected Minimal Dominating Set},
booktitle = {Proceedings of the 27th International Conference on Distributed Computing Systems Workshops},
series = {ICDCSW'07},
year = {2007},
isbn = {0-7695-2838-4},
pages = {3--11},
url = {http://dx.doi.org/10.1109/ICDCSW.2007.73},
doi = {10.1109/ICDCSW.2007.73},
acmid = {1271008},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA},
}

@inproceedings{SEK08,
author = {Sun, Huang and Effantin, Brice and Kheddouci, Hamamache},
title = {A Self-stabilizing Algorithm for the Minimum Color Sum of a Graph},
booktitle = {Proceedings of the 9th International Conference on Distributed Computing and Networking},
series = {ICDCN'08},
year = {2008},
isbn = {3-540-77443-2, 978-3-540-77443-3},
location = {Kolkata, India},
pages = {209--214},
numpages = {6},
url = {http://dl.acm.org/citation.cfm?id=1785854.1785878},
acmid = {1785878},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}

@article{SS93,
author = {Sur, Sumit and Srimani, Pradip K.},
title = {A Self-stabilizing Algorithm for Coloring Bipartite Graphs},
journal = {Information Sciences},
issue_date = {April 15, 1993},
volume = {69},
number = {3},
month = apr,
year = {1993},
issn = {0020-0255},
pages = {219--227},
numpages = {9},
url = {http://dx.doi.org/10.1016/0020-0255(93)90121-2},
doi = {10.1016/0020-0255(93)90121-2},
acmid = {161611},
publisher = {Elsevier Science Inc.},
address = {New York, NY, USA},
}

@article{TJH07,
author = {Tzeng, Chi-Hung and Jiang, Jehn-Ruey and Huang, Shing-Tsaan},
title = {A Self-stabilizing $(\Delta+4)$-edge-coloring Algorithm for Planar Graphs in Anonymous Uniform Systems},
journal = {Information Processing Letters},
issue_date = {February, 2007},
volume = {101},
number = {4},
month = feb,
year = {2007},
issn = {0020-0190},
pages = {168--173},
numpages = {6},
url = {http://dx.doi.org/10.1016/j.ipl.2006.09.004},
doi = {10.1016/j.ipl.2006.09.004},
acmid = {1223495},
publisher = {Elsevier North-Holland, Inc.},
address = {Amsterdam, The Netherlands, The Netherlands},
keywords = {Distributed systems, Edge coloring, Planar graphs, Self-stabilization},
}

@inproceedings{IKK02,
author = {Michiyo Ikeda and Sayaka Kamei and Hirotsugu Kakugawa},
title = {A Space-Optimal Self-Stabilizing Algorithm for the Maximal Independent Set Problem},
booktitle = {Proceedings of the 3rd International Conference on Parallel and Distributed Computing, Applications and Technologies},
series = {PDCAT'02},
year = {2002},
pages = {70--74},
}



@article{DT09,
author = {Dolev, Shlomi and Tzachar, Nir},
title = {Empire of Colonies: Self-stabilizing and Self-organizing Distributed Algorithm},
journal = {Theoretical Computer Science},
issue_date = {February, 2009},
volume = {410},
number = {6--7},
month = feb,
year = {2009},
issn = {0304-3975},
pages = {514--532},
numpages = {19},
url = {http://dx.doi.org/10.1016/j.tcs.2008.10.006},
doi = {10.1016/j.tcs.2008.10.006},
acmid = {1498550},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
keywords = {Clustering, Communication and routing, Self-organizing, Self-stabilizing},
}

@article{Kar01,
author = {Karaata, Mehmet Hakan},
title = {Self-Stabilizing Strong Fairness Under Weak Fairness},
journal = {IEEE Transactions on Parallel and Distributed Systems},
issue_date = {April 2001},
volume = {12},
number = {4},
month = apr,
year = {2001},
issn = {1045-9219},
pages = {337--345},
numpages = {9},
url = {http://dx.doi.org/10.1109/71.920585},
doi = {10.1109/71.920585},
acmid = {377016},
publisher = {IEEE Press},
address = {Piscataway, NJ, USA},
keywords = {Distributed systems, fairness, self-stabilization, strong fairness, schedulers.},
}

@article{NA02,
author = {Nesterenko, Mikhail and Arora, Anish},
title = {Stabilization-preserving Atomicity Refinement},
journal = {Journal of Parallel and Distributed Computing},
issue_date = {May 2002},
volume = {62},
number = {5},
month = may,
year = {2002},
issn = {0743-7315},
pages = {766--791},
numpages = {26},
url = {http://dx.doi.org/10.1006/jpdc.2001.1828},
doi = {10.1006/jpdc.2001.1828},
acmid = {638827},
publisher = {Academic Press, Inc.},
address = {Orlando, FL, USA},
keywords = {atomicity refinement, concurrency, fault-tolerance, stabilization},
}

@article{DIM97,
year={1997},
journal={SIAM Journal on Computing},
volume={26},
number={1},
title = {Resource Bounds for Self-Stabilizing Message-Driven Protocols},
author={Dolev, Shlomi and Israeli, Amos and Moran, Shlomo},
pages={273--290},
month = feb,
}

@book{GJ79,
author = {Garey, Michael R. and Johnson, David S.},
title = {Computers and Intractability: A Guide to the Theory of NP-Completeness},
year = {1979},
publisher = {W. H. Freeman \& Co.},
address = {New York, NY, USA},
}

@article{MP94,
author = {McKay,Brendan D. and Praeger,Cheryl E.},
title = {Vertex-transitive graphs which are not Cayley graphs, {I}},
journal = {Journal of the Australian Mathematical Society (Series A)},
volume = {56},
issue = {01},
month = feb,
year = {1994},
issn = {1446-8107},
pages = {53--63},
numpages = {11},
doi = {10.1017/S144678870003473X},
URL = {http://journals.cambridge.org/article_S144678870003473X},
}