Article

Free access

A faster distributed algorithm for computing maximal matchings deterministically

Authors:

Michał Hańćkowiak,

Michał Karoński,

Alessandro PanconesiAuthors Info & Claims

PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing

Pages 219 - 228

https://doi.org/10.1145/301308.301360

Published: 01 May 1999 Publication History

First page of PDF

References

[1]

B. Awerbuch, A.V. Goldberg, M. Luby, and S. Plotkin, Network decomposition and locality in distributed computing, in Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS 1989), pages 364-369, IEEE, Research Triangle Park, North Carolina.

Digital Library

[2]

B. Awerbuch, B. Berger, L. Cowen, and D. Peleg, Fast network decompositions, in Proceedings of the 1992 ACM Symposium on Principles of Distributed Computing (PODC 92), pp.169- 177

Digital Library

[3]

N. Alon, J. Spencer, and P. ErdSs, The Probabilistic Method, Wiley-Interscience Series, John Wiley & Sons, Inc., New York, 1992.

[4]

B. BollobAs, Graph Theory, Springer Verlag, New York, 1979.

[5]

B. BoUob~s, Chromatic number, girth, and maximal degree, Discrete Math. 24 (1978), 311-314.

[6]

R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70 (1986), 32- 53

Digital Library

[7]

A.V. Goldberg, S.A. Plotkin and G.E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM J. Disc. Math. Vol.1, No. 4, November 1988, pp. 434-446

Digital Library

[8]

D.A. Grable and A. Panconesi, Nearly optireal distributed edge colouring in O(loglogn) rounds, Random Structures and Algorithms, 10(3):385-405, May 1997. Preliminary version in Proceedings of the Eight Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 97), New Orleans.

Digital Library

[9]

M. Hafi~kowiak, M. Karofiski and A. Panconesi, On the distributed complexity of computing maximal matchings, in Proceedings of SODA 98, the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, pp. 219-225.

Digital Library

[10]

A. Israeli and Y. Shiloach, An improved algorithm for maximal matching, Information Proceasing Letters, 22(2):57-60, 18 January 1986

Digital Library

[11]

H.J. Karloff and D.B. Shmoys, Efficient parallel algorithms for edge coloring problems, J. Algorithms, 8 (1987), pp. 39-52

Digital Library

[12]

R. M. Karp, Probabilistic recurrence relations, in proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC 91), pages 190--197, New Orleans, Louisiana.

Digital Library

[13]

S. Kutten and D. Peleg, Fast distributed construction of k-dominating sets and applications, in Proceedings of the 1995 ACM Symposium on Principles of Distributed Computing (PODC 95), Ottawa, Ontario, pp. 238-249

Digital Library

[14]

N. Lynch, Distributed Algorithms, Morgan- Kaufmann, San Prancisco.

Digital Library

[15]

Lecture Notes in Distributed Algorithms, Solution Sheet # 4,Available at http: // www.nada, kth.se/kurser/kth/2D5340.

[16]

N. Linial, Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193- 201, February 1992.

Digital Library

[17]

N. Linial and M. Saks, Low diameter graph decomposition, Combinatorica (1993), Vol. 13 (4)

[18]

M. Luby, A simple parallel algorithm for the maximal independent set problem. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC 85), pages 1-10, Providence, Rhode Islands.

Digital Library

[19]

M. Luby, Removing randomness in parallel without processor penalty, Journal of Computer and System Sciences, 47(2):250-286, October 1993

Digital Library

[20]

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Digital Library

[21]

Moni Naor, A lower bound on probabilistic algorithms for distributive ring coloring, SIAM J. Disc. Math., Vol. 4, No. 3, pp. 409-412, August 1991

[22]

M. Naor and L. Stockmeyer, What can be computed locally? SIAM Journal on Computing, 24(6):1259-1277, December 1995.

Digital Library

[23]

O. Johausson, personal communication.

[24]

A. Panconesi, Lecture Notes in (Theoretical) Distributed Computing, KTn NADA Tech Reprt TRITA-NA-9$01

[25]

A. Panc~nesi and A. Srinivasan, The Local Nature of A-coloring and Its Algorithmic Applications, Combinatorica 15 (2) 1995, 255-280.

[26]

A. Panconesi and A. Srinivasan, On the complexity of Distributed Network Decomposition, Journal of Algorithms 20, 356-374 (1996).

Digital Library

Cited By

Czygrinow AHanćkowiak MRumiński AWitkowski M(2024)Distributed approximation for f-matchingTheoretical Computer Science10.1016/j.tcs.2024.114760(114760)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114760
Halldórsson MKöhler SPatt-Shamir BRawitz D(2018)Distributed backup placement in networksDistributed Computing10.5555/3198388.319838931:2(83-98)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.5555/3198388.3198389
Czumaj AŁącki JMądry AMitrović SOnak KSankowski PDiakonikolas IKempe DHenzinger M(2018)Round compression for parallel matching algorithmsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188764(471-484)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188764
Show More Cited By

Index Terms

A faster distributed algorithm for computing maximal matchings deterministically
1. Computer systems organization
  1. Architectures
    1. Distributed architectures

Recommendations

Distributed maximal matching: greedy is optimal
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with k colours, there is a trivial greedy algorithm that finds a maximal matching in k-1 synchronous communication ...
On the Distributed Complexity of Computing Maximal Matchings

We show that maximal matchings can be computed deterministically in O(log⁴ n) rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a nontrivial graph structure, and the only "classical" one, which ...
Lower Bounds for Maximal Matchings and Maximal Independent Sets
There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Δ + log^* n) communication rounds; here, n is the number of nodes and Δ is the maximum degree. The lower bound by Linial (1987, 1992) shows that the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '99: Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing

May 1999

286 pages

ISBN:1581130996

DOI:10.1145/301308

Chairmen:
Brian Coan
Bellcore, Morristown, NJ
,
Jennifer Welch
Texas A & M Univ., College Station

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC99

Sponsor:

PODC99: ACM Symposium on Principles of Distributed Computing

May 4 - 6, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
573
Total Downloads

Downloads (Last 12 months)53
Downloads (Last 6 weeks)6

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Czygrinow AHanćkowiak MRumiński AWitkowski M(2024)Distributed approximation for f-matchingTheoretical Computer Science10.1016/j.tcs.2024.114760(114760)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114760
Halldórsson MKöhler SPatt-Shamir BRawitz D(2018)Distributed backup placement in networksDistributed Computing10.5555/3198388.319838931:2(83-98)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.5555/3198388.3198389
Czumaj AŁącki JMądry AMitrović SOnak KSankowski PDiakonikolas IKempe DHenzinger M(2018)Round compression for parallel matching algorithmsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188764(471-484)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188764
Fischer M(2018)Improved deterministic distributed matching via roundingDistributed Computing10.1007/s00446-018-0344-4Online publication date: 4-Oct-2018
https://doi.org/10.1007/s00446-018-0344-4
Kuhn FMaus YWeidner S(2018)Deterministic Distributed Ruling Sets of Line GraphsStructural Information and Communication Complexity10.1007/978-3-030-01325-7_19(193-208)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-3-030-01325-7_19
Halldórsson MKöhler SPatt-Shamir BRawitz D(2017)Distributed backup placement in networksDistributed Computing10.1007/s00446-017-0299-x31:2(83-98)Online publication date: 3-Jun-2017
https://doi.org/10.1007/s00446-017-0299-x
Lotker ZPatt-Shamir BPettie S(2015)Improved Distributed Approximate MatchingJournal of the ACM10.1145/278675362:5(1-17)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2786753
Halldórsson MKöhler SPatt-Shamir BRawitz DBlelloch GAgrawal K(2015)Distributed Backup Placement in NetworksProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755583(274-283)Online publication date: 13-Jun-2015
https://dl.acm.org/doi/10.1145/2755573.2755583
Lotker ZPatt-Shamir BPettie SMeyer auf der Heide FShavit N(2008)Improved distributed approximate matchingProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378558(129-136)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1145/1378533.1378558
Czygrinow AHańckowiak MWawrzyniak WMeyer auf der Heide FShavit N(2008)Distributed packing in planar graphsProceedings of the twentieth annual symposium on Parallelism in algorithms and architectures10.1145/1378533.1378541(55-61)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1145/1378533.1378541
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents