Efficient Distributed Weighted Matchings on Trees

• Jaap-Henk Hoepman
• Shay Kutten
• Zvi Lotker
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)

Abstract

In this paper, we study distributed algorithms to compute a weighted matching that have constant (or at least sub-logarithmic) running time and that achieve approximation ratio 2 + ε or better. In fact we present two such synchronous algorithms, that work on arbitrary weighted trees.

The first algorithm is a randomised distributed algorithm that computes a weighted matching of an arbitrary weighted tree, that approximates the maximum weighted matching by a factor 2 + ε. The running time is O(1). The second algorithm is deterministic, and approximates the maximum weighted matching by a factor 2 + ε, but has running time O(log* |V|). Our algorithms can also be used to compute maximum unweighted matchings on regular and almost regular graphs within a constant approximation.

Keywords

Approximation Ratio Regular Graph General Graph Maximum Match Constant Approximation
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

1. [Avi83]
Avis, D.: A survey of heuristics for the weighted matching problem. Networks 13, 475–493 (1983)
2. [CHS02]
Chattopadhyay, S., Higham, L., Seyffarth, K.: Dynamic and self-stabilizing distributed matching. In: 21st PODC, Monterey, CA, USA, pp. 290–297. ACM Press, New York (2002)Google Scholar
3. [Gab90]
Gabow, H.: Data structures for weighted matching and nearest common ancestors with linking. In: 1st SODA, San Fransisco, Ca., USA, pp. 434–443. ACM Press, New York (1990)Google Scholar
4. [GPS87]
Goldberg, A.V., Plotkin, S., Shannon, G.: Parallel symmetry breaking in sparse graphs. In: 19th STOC, New York City, NY, USA. ACM Press, New York (1987)Google Scholar
5. [Hoe04]
Hoepman, J.-H. Simple distributed weighted matchings, eprint cs.DC/0410047 (2004)Google Scholar
6. [II86]
Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Proc. Letters 22, 77–80 (1986)
7. [KS00]
Karaata, M., Saleh, K.: A distributed self-stabilizing algorithm for finding maximal matching. Computer Systems Science and Engineering 3, 175–180 (2000)Google Scholar
8. [KP98]
Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. Journal of Algorithms 28(1), 40–66 (1998)
9. [MV80]
Micali, S., Vazirani, V.: An $$O(\sqrt{V}E)$$ algorithm for finding maximum matching in general graphs. In: 21st FOCS, Syracuse, NY, USA, pp. 17–27. IEEE Computer Society Press, Los Alamitos (1980)Google Scholar
10. [Pre99]
Preis, R.: Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 259–269. Springer, Heidelberg (1999)
11. [UC00]
Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. Inf. Proc. Letters 76, 13–17 (2000)
12. [WW04]
Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: Guerraoui, R. (ed.) DISC 2004. LNCS, vol. 3274, pp. 335–348. Springer, Heidelberg (2004)

Authors and Affiliations

• Jaap-Henk Hoepman
• 1
• Shay Kutten
• 2
• Zvi Lotker
• 3
1. 1.Institute for Computing and Information SciencesRadboud University NijmegenNijmegenThe Netherlands
2. 2.Faculty of Industrial Engineering and ManagementTechnionHaifaIsrael
3. 3.CWIAmsterdamThe Netherlands