No Access

A Self-Stabilizing Algorithm for a Maximal 2-Packing in a Cactus Graph Under Any Scheduler

CONACYT-Centro de Investigación en Matemáticas A.C., CIMAT-Mérida, 97032, Sierra Papacal, Mérida, Yucatán, México

Department of Computer Science, CICESE, Carretera Ensenada-Tijuana No. 3918, Zona Playitas, C.P. 22860, Ensenada, B.C., México

E-mail Address: [email protected]

Search for more papers by this author

, and

Julio César Ramírez-Pacheco

Department of Basic Sciences, Universidad del Caribe, SM. 78, Mza. 1, Lote 1, Esquina Fraccionamiento Tabachines, 77528 Cancún, Q.R., México

E-mail Address: [email protected]

Search for more papers by this author

https://doi.org/10.1142/S012905411750037XCited by:2 (Source: Crossref)

Abstract

In this paper, we present a self-stabilizing algorithm that computes a maximal 2-packing set in a cactus under the adversarial scheduler. The cactus is a network topology such that any edge belongs to at most one cycle. The cactus has important applications in telecommunication networks, location problems, and biotechnology, among others. We assume that the value of each vertex identifier can take any value of length $O (log n)$ bits. The execution time of this algorithm is $O (n)$ rounds or $O (n^{2})$ time steps. Our algorithm matches the state of the art results for this problem, following an entirely different approach. Our approach allows the computation of the maximum 2-packing when the cactus is a ring.

Communicated by Shlomo Moran

Keywords:

References

1. B. Ben-Moshe, B. Bhattacharya and Q. Shi , Efficient algorithms for the weighted 2-center problem in a cactus graph, Algorithms and Computation (Springer, Berlin, Heidelberg, 2005), pp. 693–703. Crossref, Google Scholar
2. A. K. Datta, L. L. Larmore and P. Vemula , Self-stabilizing leader election in optimal space under an arbitrary scheduler, Theoretical Computer Science 412(40) (2011) 5541–5561. Crossref, Web of Science, Google Scholar
3. E. W. Dijkstra , Self-stabilizing systems in spite of distributed control, Commun. ACM 17 (November 1974) 643–644. Crossref, Web of Science, Google Scholar
4. Y. Ding, J. Wang and P. K. Srimani , Self-stabilizing algorithms for maximal 2-packing and general k-packing (k 2) with safe convergence in an arbitrary graph, International Journal of Networking and Computing 5(1) (2015) 105–121. Crossref, Google Scholar
5. M. Gairing, R. M. Geist, S. T. Hedetniemi and P. Kristiansen , A self-stabilizing algorithm for maximal 2-packing, Nordic J. of Computing 11(1) (2004) 1–11. Google Scholar
6. F. C. Gärtner, A survey of self-stabilizing spanning-tree construction algorithms, tech. rep. (2003). Google Scholar
7. W. Goddard, S. T. Hedetniemi, D. P. Jacobs and V. Trevisan , Distance-k knowledge in self-stabilizing algorithms, Theoretical Computer Science 399(1) (2008) 118–127. Crossref, Web of Science, Google Scholar
8. M. G. Gouda and N. J. Multari , Stabilizing communication protocols, Computers, IEEE Transactions on 40(4) (1991) 448–458. Crossref, Web of Science, Google Scholar
9. S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs and P. K. Srimani , Self-stabilizing algorithms for minimal dominating sets and maximal independent sets, Computers & Mathematics with Applications 46(5) (2003) 805–811. Crossref, Web of Science, Google Scholar
10. O. Kariv and S. L. Hakimi , An algorithmic approach to network location problems. i: The p-centers, SIAM Journal on Applied Mathematics 37(3) (1979) 513–538. Crossref, Web of Science, Google Scholar
11. W. Koontz , Economic evaluation of loop feeder relief alternatives, Bell System Technical Journal 59(3) (1980) 277–293. Crossref, Google Scholar
12. Y.-F. Lan and Y.-L. Wang , An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs, European Journal of Operational Research 122(3) (2000) 602–610. Crossref, Web of Science, Google Scholar
13. F. Manne and M. Mjelde , A memory efficient self-stabilizing algorithm for maximal k-packing, Proceedings of the 8th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS’06 (Springer-Verlag, Berlin, Heidelberg, 2006), pp. 428–439. Google Scholar
14. M. Mjelde, K-packings and k-dominations on tree graphs (2004), Chair-Pardalos, Panagote M. Google Scholar
15. B. Paten, M. Diekhans, D. Earl, J. S. John, J. Ma, B. Suh and D. Haussler , Cactus graphs for genome comparisons, Journal of Computational Biology 18(3) (2011) 469–481. Crossref, Web of Science, Google Scholar
16. Z. Shi , A self-stabilizing algorithm to maximal 2-packing with improved complexity, Information Processing Letters 112(13) (2012) 525–531. Crossref, Web of Science, Google Scholar
17. Z. Shi, W. Goddard and S. T. Hedetniemi , An anonymous self-stabilizing algorithm for 1-maximal independent set in trees, Information Processing Letters 91(2) (2004) 77–83. Crossref, Web of Science, Google Scholar
18. J. A. Trejo-Sánchez and J. A. Fernández-Zepeda , A self-stabilizing algorithm for the maximal 2-packing in a cactus graph, IPDPS Workshops (IEEE Computer Society, 2012), pp. 863–871. Google Scholar
19. J. A. Trejo-Sánchez and J. A. Fernández-Zepeda , Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs, Journal of Parallel and Distributed Computing 74(3) (2014) 2193–2202. Crossref, Web of Science, Google Scholar
20. V. Turau , Efficient transformation of distance-2 self-stabilizing algorithms, Journal of Parallel and Distributed Computing 72(4) (2012) 603–612. Crossref, Web of Science, Google Scholar
21. R. Uehara and Y. Uno , On computing longest paths in small graph classes, International Journal of Foundations of Computer Science 18(05) (2007) 911–930. Link, Web of Science, Google Scholar
22. B. Zmazek and J. Žerovnik , The obnoxious center problem on weighted cactus graphs, Discrete Applied Mathematics 136(2) (2004) 377–386. Crossref, Web of Science, Google Scholar
23. B. Zmazek and J. Žerovnik , Estimating the traffic on weighted cactus networks in linear time, Information Visualisation, 2005, Proceedings. Ninth International Conference on, IEEE (2005), pp. 536–541. Google Scholar