Abstract
The graph partitioning problem consists of dividing a graph into parts, patterns or partitions which satisfy some specifications. Graph partitioning problems are known to be NP-complete. In this paper, we focus on the particular pattern of triangles and present the first Self-stabilizing algorithm for Maximal Partitioning of arbitrary graphs into Triangles (MPT). Then, we give the correctness and convergence proofs of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Al-Azemi, F.M., Karaata, M.H.: Brief Announcement: A Stabilizing Algorithm for Finding Two Edge-Disjoint Paths in Arbitrary Graphs. In: Défago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 433–434. Springer, Heidelberg (2011)
Andreev, K., Räcke, H.: Balanced graph partitioning. In: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2004, pp. 120–124 (2004)
Beauquier, J., Datta, A.K., Gradinariu, M., Magniette, F.: Self-Stabilizing Local Mutual Exclusion and Daemon Refinement. In: Herlihy, M.P. (ed.) DISC 2000. LNCS, vol. 1914, pp. 223–237. Springer, Heidelberg (2000)
Bein, D., Datta, A.K., Jagganagari, C.R., Villain, V.: A self-stabilizing link-cluster algorithm in mobile ad hoc networks. In: ISPAN, pp. 436–441 (2005)
Belkouch, F., Bui, M., Chen, L., Datta, A.K.: Self-stabilizing deterministic network decomposition. J. Parallel Distrib. Comput. 62(4), 696–714 (2002)
Blin, L., Potop-Butucaru, M.G., Rovedakis, S., Tixeuil, S.: Loop-Free Super-Stabilizing Spanning Tree Construction. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 50–64. Springer, Heidelberg (2010)
Caron, E., Datta, A.K., Depardon, B., Larmore, L.L.: A Self-stabilizing K-Clustering Algorithm Using an Arbitrary Metric. In: Sips, H., Epema, D., Lin, H.-X. (eds.) Euro-Par 2009. LNCS, vol. 5704, pp. 602–614. Springer, Heidelberg (2009)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)
Dolev, S.: Self-stabilization. MIT Press (2000)
Dubois, S., Tixeuil, S.: A taxonomy of daemons in self-stabilization. CoRR, abs/1110.0334 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: Anonymous Daemon Conversion in Self-stabilizing Algorithms by Randomization in Constant Space. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 182–190. Springer, Heidelberg (2008)
Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: A robust distributed generalized matching protocol that stabilizes in linear time. In: ICDCS Workshops, pp. 461–465 (2003)
Goddard, W., Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. In: IPDPS, p. 162 (2003)
Gradinariu, M., Tixeuil, S.: Conflict managers for self-stabilization without fairness assumption. In: Proceedings of the 27th International Conference on Distributed Computing Systems, ICDCS 2007, Washington, DC, USA, p. 46 (2007)
Guellati, N., Kheddouci, H.: A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. J. Parallel Distrib. Comput. (4), 406–415 (2010)
Hadid, R., Karaata, M.H.: An adaptive stabilizing algorithm for finding all disjoint paths in anonymous mesh networks. Computer Communications 32(5), 858–866 (2009)
Hadid, R., Karaata, M.H.: Stabilizing maximum matching in bipartite networks. Computing 84(1-2), 121–138 (2009)
Karaata, M.H.: An optimal self-stabilizing strarvation-free alternator. J. Comput. Syst. Sci. 71(4), 480–494 (2005)
Hedetniemi, S.T., Jacobs, D.P., Srimani, P.K.: Maximal matching stabilizes in time o(m). Inf. Process. Lett. 80(5), 221–223 (2001)
Hsu, S.-C., Huang, S.-T.: A self-stabilizing algorithm for maximal matching. Inf. Process. Lett. 43(2), 77–81 (1992)
Ishii, H., Kakugawa, H.: A self-stabilizing algorithm for finding cliques in distributed systems. In: IEEE Symposium on Reliable Distributed Systems, vol. 0, p. 390 (2002)
Karaata, M.H., Hadid, R.: Brief Announcement: A Stabilizing Algorithm for Finding Two Disjoint Paths in Arbitrary Networks. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol. 5873, pp. 789–790. Springer, Heidelberg (2009)
Manne, F., Mjelde, M., Pilard, L., Tixeuil, S.: A new self-stabilizing maximal matching algorithm. Theor. Comput. Sci. 410(14), 1336–1345 (2009)
Pothen, A.: Graph partitioning algorithms with applications to scientific computing. Technical report, Norfolk, VA, USA (1997)
Serrour, B., Arenas, A., Gomez, S.: Detecting communities of triangles in complex networks using spectral optimization. Computer Communications 34(5), 629–634 (2011)
Tel, G.: Maximal matching stabilizes in quadratic time. Inf. Process. Lett. 49(6), 271–272 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Neggazi, B., Haddad, M., Kheddouci, H. (2012). Self-stabilizing Algorithm for Maximal Graph Partitioning into Triangles. In: Richa, A.W., Scheideler, C. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2012. Lecture Notes in Computer Science, vol 7596. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33536-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-33536-5_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-33535-8
Online ISBN: 978-3-642-33536-5
eBook Packages: Computer ScienceComputer Science (R0)