Concepedia

Maximum Matching Approximation

Maximum Matching Approximation is a method in approximation algorithms that belongs to the class of greedy algorithms, differing by specifically addressing the problem of finding a matching in a graph that is guaranteed to be within a certain factor of the maximum possible size.

179

Publications

15.4K

Citations

329

Authors

189

Institutions

Publications per year

2017–2026

30

Parents

Publications

179

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

John E. Hopcroft, Richard M. Karp · SIAM Journal on Computing · 1973 · 2.8K citations

, , +15

Paths, Trees, and Flowers

Jack Edmonds · Canadian Journal of Mathematics · 1965 · 2.4K citations · Full text

, , +16

Maximum matching and a polyhedron with 0,1-vertices

Jack Edmonds · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · 1965 · 1.7K citations · Full text

, , +8

Algorithms for Loop Matchings

Ruth Nussinov, George Pieczenik, Jerrold R. Griggs et al. · SIAM Journal on Applied Mathematics · 1978 · 603 citations

, , +12

An O (N2.5) algorithm for maximum matching in general graphs

Shimon Even, Oded Kariv · 1975 · 296 citations

, , +9

1–5 of 179

Authors

329

  1. SK
    Sanjeev Khanna

    University of Pennsylvania, United States

    11 publications · 448 citations

    11

    h-index

  2. SA
    Sepehr Assadi

    University of Pennsylvania, United States

    9 publications · 269 citations

    9

    h-index

  3. MM
    Morteza Monemizadeh

    University of Warwick, United Kingdom

    6 publications · 105 citations

    6

    h-index

  4. MH
    MohammadTaghi Hajiaghayi

    University of Maryland, College Park, United States

    6 publications · 133 citations

    6

    h-index

  5. MK
    Michael Kapralov

    Stanford University, United States

    6 publications · 382 citations

    6

    h-index

1–5 of 329

Institutions

189

  1. Tel Aviv University

    Tel Aviv, Israel

    10 h-index

    17 publications

    392 citations

  2. University of Pennsylvania

    Philadelphia, United States

    10 h-index

    21 publications

    937 citations

  3. Stanford University

    Stanford, United States

    7 h-index

    10 publications

    711 citations

  4. Rutgers, The State University of New Jersey

    New Brunswick, United States

    6 h-index

    8 publications

    266 citations

  5. University of Maryland, College Park

    College Park, United States

    6 h-index

    15 publications

    398 citations

  6. Centre National de la Recherche Scientifique

    Paris, France

    5 h-index

    12 publications

    295 citations

  7. ETH Zurich

    Zurich, Switzerland

    5 h-index

    7 publications

    315 citations

  8. University of California, Berkeley

    Berkeley, United States

    5 h-index

    6 publications

    777 citations

1–8 of 189

Venues

  1. arXiv (Cornell University)

    Repository · 15 publications · 327 citations

    12

    h-index

  2. Information Processing Letters

    12 publications · 777 citations

    10

    h-index

  3. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 9 publications · 166 citations

    9

    h-index

  4. Discrete Mathematics

    5 publications · 196 citations

    5

    h-index

  5. Theoretical Computer Science

    5 publications · 139 citations

    5

    h-index

1–5