Document Open Access Logo

Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3

Authors Johanne Cohen, Khaled Maâmra, George Manoussakis, Laurence Pilard

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.11.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Johanne Cohen
Khaled Maâmra
George Manoussakis
Laurence Pilard

Cite As Get BibTex

Johanne Cohen, Khaled Maâmra, George Manoussakis, and Laurence Pilard. Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.11

Abstract

We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).

Subject Classification

Keywords
  • Self-Stabilization
  • Distributed Algorithm
  • Fault Tolerance
  • Matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Y. Asada and M. Inoue. An efficient silent self-stabilizing algorithm for 1-maximal matching in anonymous networks. In WALCOM: Algorithms and Computation - 9th International Workshop, pages 187-198. Springer International Publishing, 2015. Google Scholar
  2. P. Berenbrink, T. Friedetzky, and R. A. Martin. On the stability of dynamic diffusion load balancing. Algorithmica, 50(3):329-350, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9081-y.
  3. J. Cohen, K. Maamra, G. Manoussakis, and L. Pilard. The Manne et al. self-stabilizing 2/3-approximation matching algorithm is sub-exponential. CoRR, abs/1604.08066, 2016. URL: http://arxiv.org/abs/1604.08066.
  4. J. Cohen, K. Maamra, G. Manoussakis, and L. Pilard. Polynomial self-stabilizing algorithm and proof for a 2/3-approximation of a maximum matching. CoRR, abs/1611.06038, 2016. URL: http://arxiv.org/abs/1611.06038.
  5. S. Dolev. Self-Stabilization. MIT Press, 2000. Google Scholar
  6. D. E. Drake and S. Hougardy. A simple approximation algorithm for the weighted matching problem. Inf. Process. Lett., 85(4):211-213, 2003. Google Scholar
  7. B. Ghosh and S. Muthukrishnan. Dynamic load balancing by random matchings. J. Comput. Syst. Sci., 53(3):357-370, 1996. URL: http://dx.doi.org/10.1006/jcss.1996.0075.
  8. N. Guellati and H. Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. J. Parallel Distrib. Comput., 70(4):406-415, 2010. Google Scholar
  9. S. T. Hedetniemi, D. Pokrass Jacobs, and P. K. Srimani. Maximal matching stabilizes in time o(m). Inf. Process. Lett., 80(5):221-223, 2001. Google Scholar
  10. M. Hoefer. Local matching dynamics in social networks. Inf. Comput., 222:20-35, 2013. Google Scholar
  11. J. E. Hopcroft and R. M. Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4):225-231, 1973. Google Scholar
  12. S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal matching. Inf. Process. Lett., 43(2):77-81, 1992. Google Scholar
  13. D. Knuth. Marriages stables et leurs relations avec d'autres problèmes combinatoires. Les Presses de l'Université de Montréal, 1976. Google Scholar
  14. F. Manne and M. Mjelde. A self-stabilizing weighted matching algorithm. In 9th Int. Symposium Stabilization, Safety, and Security of Distributed Systems (SSS), Lecture Notes in Computer Science, pages 383-393. Springer, 2007. Google Scholar
  15. F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A new self-stabilizing maximal matching algorithm. Theoretical Computer Science (TCS), 410(14):1336-1345, 2009. Google Scholar
  16. F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A self-stabilizing 2/3-approximation algorithm for the maximum matching problem. Theoretical Computer Science (TCS), 412(40):5515-5526, 2011. Google Scholar
  17. R. Preis. Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, pages 259-269. Springer, 1999. Google Scholar
  18. M. Touati, R. El-Azouzi, M. Coupechoux, E. Altman, and J. M. Kelif. Controlled matching game for user association and resource allocation in multi-rate wlans? In 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 372-380, Sept 2015. URL: http://dx.doi.org/10.1109/ALLERTON.2015.7447028.
  19. V. Turau and B. Hauck. A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2. Theoretical Computer Science (TCS), 412(40):5527-5540, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact