Document Open Access Logo

Maximum Matching for Anonymous Trees with Constant Space per Process

Authors Ajoy K. Datta, Lawrence L. Larmore, Toshimitsu Masuzawa

PDF

File

Thumbnail PDF
PDF
LIPIcs.OPODIS.2015.16.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Subject Classification

Keywords
  • anonymous tree
  • maximum matching
  • self-stabilization
  • unfair daemon

Metrics

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

Abstract

We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.

Cite As Get BibTex

Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Maximum Matching for Anonymous Trees with Constant Space per Process. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.OPODIS.2015.16

Author Details

Ajoy K. Datta
Lawrence L. Larmore
Toshimitsu Masuzawa

References

  1. Y. Asada and M. Inoue. A silent self-stabilizing algorithm for 1-maximal matching in anonymous networks. In Proc. WALCOM 2015, pages 187-198, 2015. Google Scholar
  2. J.R.S. Blair and F. Manne. Efficient self-stabilizing algorithms for tree networks. In Proc. ICDCS 2003, pages 20-26, 2003. Google Scholar
  3. S. Chattopadhyay, L. Higham, and K. Seyffarth. Dynamic and self-stabilizing. In Proc. PODC 2002, pages 290-297, 2002. Google Scholar
  4. A. K. Datta and L. L. Larmore. Leader election and centers and medians in tree networks. In Proc. SSS 2013, pages 113-132, 2013. Google Scholar
  5. E.W. Dijkstra. Self stabilizing systems in spite of distributed control. Communications of the ACM, 17:643-644, 1974. Google Scholar
  6. W. Goddard, S.T. Hedetniemi, D.P. Jacobs, and P.K. Srimani. Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks. In Proc. IPDPS 2003, page 162, 2003. Google Scholar
  7. W. Goddard, S.T. Hedetniemi, and Z. Shi. An anonymous self-stabilizing algorithm for 1-maximal matching in trees. In Proc. PDPTA 2006, pages 797-803, 2006. Google Scholar
  8. N. Guellati and H. Kheddouci. A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs. Journal of Parallel and Distributed Computing, 70(4):406-415, 2010. Google Scholar
  9. S.T. Hedetniemi, D.P. Jacobs, and P.K. Srimani. Maximal matching stabilizes in time O(m). Information Processing Letters, 80(5):221-223, 2001. Google Scholar
  10. S.C. Hsu and S.T. Huang. A self-stabilizing algorithm for maximal matching. Information Processing Letters, 43(2):77-81, 1992. Google Scholar
  11. M.H. Karaata and K.A. Saleh. A distributed self-stabilizing algorithm for finding maximum matching. Computer Systems Science and Engineering, 15(3):175-180, 2000. Google Scholar
  12. M. Kimoto, T. Tsuchiya, and T. Kikuno. The time complexity of Hsu and Huang’s self-stabilizing maximal matching algorithm. IEICE Trans. Infrmation and Systems, E93-D(10):2850-2853, 2010. Google Scholar
  13. F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A new self-stabilizing maximal matching algorithm. In Proc. SIROCCO 2007, pages 96-108, 2007. Google Scholar
  14. F. Manne, M. Mjelde, L. Pilard, and S. Tixeuil. A self-stabilizing 2/3-approximation algorithm for the maximum matching problem. Theoretical Computer Science, 412(4):5515-5526, 2011. Google Scholar
  15. G. Tel. Maximal matching stabilizes in quadratic time. Information Processing Letters, 49(6):271-272, 1994. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact