A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching
References
[1]
A.V.Aho, J.E.Hopcroft and J.D.Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974.
[2]
N.Blum, A new approach to maximum matching in general graphs, Proc. 17th ICALP LNCS 443 (1990), 5s6-597.
[3]
J.Cheriyan, Random weighted Laplacians, Lovdsz minimum digraphs and finding minimum separators, extended abstract in Proc. 4th ACM- SIAM Symposium on Discrete Algorithms (1993), 31-40.
[4]
J.Cheriyan and K. Padayachee, Randomized decomposition algorithms for T-joins and matchlugs, in preparation, 1993.
[5]
D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comp., 9 (1990), 23-52.
[6]
W.Eberly, Efficient parallel independent subsets and matrix factorizations, Proc. 3rd IEEE Symposium on Parallel and Distributed Processing, (1991), 204-211.
[7]
Z. Galil and V. Pan, Improved processor bounds for combinatorial problems in RNC, Combinatorica 8 (1988), 189-200.
[8]
O. H. Ibarra, S. Moran and R. Hui, A generalization of the fast L UP matrix decomposition algorithm and applications, J. Algorithms 3 (1982), 45-56.
[9]
E. Kaltofen and V. Pan, Processor efficient parallel solution of linear syslems over an abstract field, Proc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (1991), 180-191.
[10]
H.J.Karloff, A Las Vegas RNC algorithm for maximum matching, Combinatorica 6 (1986), 387-391.
[11]
R. M. Karp, E. Upfal and A. Wigderson, Computing a perfect matching is in random NC, Combinatorica 6 (1986), 35-48.
[12]
D. Kozen, The Design and Analysis of Algorithms, Springer Verlag, Berlin, 1991.
[13]
L. Lov~sz, On determinants, matchings and random algorithms, Fundamentals of Computing Theory, L. Budach, Ed., Akademia Verlag, Berlin, (1979).
[14]
L. Lov~sz and M. Plummer, Matching Theory, Academic Press, Budapest, Hungary, (1986).
[15]
S.Micali and V.V.Vazirani, An O(l~V/Izl) algorithm for finding maximum matching in general graphs, Proc. 21st IEEE FOCS (1980), 17-27.
[16]
K. Mulmuley, U. V. Vazirani and V. V. Vazirant, Matching is as easy as matrix inversion, Combinatorica 7 (1987), 105-113.
[17]
M. O. Rabin and V. V. Vazirani, Maximum matchings in general graphs through randomization, J. Algorithms 10 (1989), 557-567.
[18]
J. T. Schwartz, Fast probabilistic algorithms for verification of polynomial identities, J. ACM 27 (1980), 701-717.
[19]
V.V.Vazirani, A theory of alternating paths and blossoms for proving correctness of the O(~/-VE) general graph matching algorithm, Technical Report 89-1035, Dept. of C.S., Cornell University, Ithaca, NY, Sept. 1989.
[20]
J. Wein, Las Vegas RNC algorithms for unary weighted perfect matching and T-join problems, Information Processing Letters 40 (1991), 161- 167.
[21]
R. E. Zippel, Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM 79, Ng, Ed., Lecture Notes in Computer Science 72, 216-226, Springer-Verlag, 1979.
Index Terms
- A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching
Recommendations
Distributed Maximum Matching in Bounded Degree Graphs
ICDCN '15: Proceedings of the 16th International Conference on Distributed Computing and NetworkingWe present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted case computes a matching whose size is at least (1−ϵ) times the optimal in ...
Distributed Approximation of Maximum Independent Set and Maximum Matching
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed ComputingWe present a simple distributed Δ-approximation algorithm for maximum weight independent set (MaxIS) in the CONGEST model which completes in O(MIS ⋅ log W) rounds, where Δ is the maximum degree, MIS is the number of rounds needed to compute a maximal ...
Parallel Maximum Matching Algorithms in Interval Graphs
ICPADS '97: Proceedings of the 1997 International Conference on Parallel and Distributed SystemsWe develop new parallel maximum matching algorithms in interval graphs by exploiting the characteristics of interval graphs. For general interval graphs, our algorithm requires O(\log^2 v+(n\log n)/v) time and O(nv^2+n^2) operations on the CREW PRAM, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
- SIAM: Society for Industrial and Applied Mathematics
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 23 January 1994
Check for updates
Qualifiers
- Article
Conference
SODA94
Sponsor:
- SIGACT
- SIAM
Acceptance Rates
Overall Acceptance Rate 411 of 1,322 submissions, 31%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 460Total Downloads
- Downloads (Last 12 months)45
- Downloads (Last 6 weeks)4
Reflects downloads up to 12 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in