3339:(BFS) from uDummy to vDummy then we can get the paths of minimal length that connect currently unmatched vertices in U to currently unmatched vertices in V. Note that, as the graph is bipartite, these paths always alternate between vertices in U and vertices in V, and we require in our BFS that when going from V to U, we always select a matched edge. If we reach an unmatched vertex of V, then we end at vDummy and the search for paths in the BFS terminate. To summarize, the BFS starts at unmatched vertices in U, goes to all their neighbors in V, if all are matched then it goes back to the vertices in U to which all these vertices are matched (and which were not visited before), then it goes to all the neighbors of these vertices, etc., until one of the vertices reached in V is unmatched.
3350:(DFS). Note that each vertex in V on such a path, except for the last one, is currently matched. So we can explore with the DFS, making sure that the paths that we follow correspond to the distances computed in the BFS. We update along every such path by removing from the matching all edges of the path that are currently in the matching, and adding to the matching all edges of the path that are currently not in the matching: as this is an augmenting path (the first and last edges of the path were not part of the matching, and the path alternated between matched and unmatched edges), then this increases the number of edges in the matching. This is same as replacing the current matching by the symmetric difference between the current matching and the entire path..
457:. These paths are sequences of edges of the graph, which alternate between edges in the matching and edges out of the partial matching, and where the initial and final edge are not in the partial matching. Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa). Simpler algorithms for bipartite matching, such as the
3322:
1224:, paths along which one may increase the amount of flow between the terminals of the flow. It is possible to transform the bipartite matching problem into a maximum flow instance, such that the alternating paths of the matching problem become augmenting paths of the flow problem. It suffices to insert two vertices, source and sink, and insert edges of unit capacity from the source to each vertex in
646:, a path that starts at a free vertex, ends at a free vertex, and alternates between unmatched and matched edges within the path. It follows from this definition that, except for the endpoints, all other vertices (if any) in augmenting path must be non-free vertices. An augmenting path could consist of only two vertices (both free) and single unmatched edge between them.
3343:
from V to U on edges that are currently part of the matching. In particular, the special NIL vertex, which corresponds to vDummy, then gets assigned a finite distance, so the BFS function returns true iff some path has been found. If no path has been found, then there are no augmenting paths left and the matching is maximal.
3117:
showed how to implement a phase in linear time, resulting in a non-bipartite matching algorithm with the same time bound as the
Hopcroft–Karp algorithm for bipartite graphs. The Micali–Vazirani technique is complex, and its authors did not provide full proofs of their results; subsequently, a "clear
3342:
Observe in particular that BFS marks the unmatched nodes of U with distance 0, then increments the distance every time it comes back to U. This guarantees that the paths considered in the BFS are of minimal length to connect unmatched vertices of U to unmatched vertices of V while always going back
3334:
Let the vertices of our graph be partitioned in U and V, and consider a partial matching, as indicated by the Pair_U and Pair_V tables that contain the one vertex to which each vertex of U and of V is matched, or NIL for unmatched vertices. The key idea is to add two dummy vertices on each side of
2058:, using the breadth first layering to guide the search: the DFS is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the DFS tree must alternate between matched and unmatched edges. Once an augmenting path is found that involves one of the vertices in
3060:
Several authors have performed experimental comparisons of bipartite matching algorithms. Their results in general tend to show that the
Hopcroft–Karp method is not as good in practice as it is in theory: it is outperformed both by simpler breadth-first and depth-first strategies for finding
3353:
Note that the code ensures that all augmenting paths that we consider are vertex disjoint. Indeed, after doing the symmetric difference for a path, none of its vertices could be considered again in the DFS, just because the Dist] will not be equal to Dist + 1 (it would be exactly Dist).
2424:
Each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial
1795:
are by definition not adjacent to any matched edges. At subsequent levels of the search, the traversed edges are required to alternate between matched and unmatched. That is, when searching for successors from a vertex in
3628:
1586:
3051:
1505:
3366:
One last observation is that we actually don't need uDummy: its role is simply to put all unmatched vertices of U in the queue when we start the BFS. As for vDummy, it is denoted as NIL in the pseudocode above.
3069:
The same idea of finding a maximal set of shortest augmenting paths works also for finding maximum cardinality matchings in non-bipartite graphs, and for the same reasons the algorithms based on this idea take
4059:
1775:
are used as the starting vertices of this search and form the first layer of the partitioning. At the first level of the search, there are only unmatched edges, since the free vertices in
1622:
1424:
3363:
When we were not able to find any shortest augmenting path from a vertex u, then the DFS marks vertex u by setting Dist to infinity, so that these vertices are not visited again.
2955:
2751:
2419:
597:
209:
3111:
502:
308:
3113:
phases. However, for non-bipartite graphs, the task of finding the augmenting paths within each phase is more difficult. Building on the work of several slower predecessors,
84:
2881:
2695:
420:
2655:
2621:
2567:
2533:
2491:
2457:
2303:
849:
1397:
1366:
358:
2823:
737:
2501:
found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least
2269:
2155:
541:
2078:, the DFS is continued from the next starting vertex. Any vertex encountered during the DFS can immediately be marked as used, since if there is no path from it to
1171:
1104:
1057:
1030:
923:
876:
773:
124:
2363:
2333:
2587:
2218:
2195:
2175:
2116:
2096:
2076:
2056:
2036:
2004:
1977:
1957:
1937:
1917:
1897:
1874:
1854:
1834:
1814:
1793:
1773:
1745:
1725:
1705:
1685:
1665:
1645:
1302:
1282:
1262:
1242:
1211:
1191:
1144:
1124:
1077:
1003:
983:
963:
943:
896:
816:
796:
707:
687:
667:
636:
253:
233:
4062:
461:‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only
1059:
is optimal. Now, the cycles and the paths with equal numbers of matched and unmatched vertices do not contribute to the difference in size between
3571:
2014:
number of such paths, which would be harder to do. Fortunately, it is sufficient here to find a maximal set of paths.) This set may be computed by
1514:
1304:
have unit capacity. A generalization of the technique used in
Hopcroft–Karp algorithm to find maximum flow in an arbitrary network is known as
3346:
If BFS returns true, then we can go ahead and update the pairing for vertices on the minimal-length paths found from U to V: we do so using a
4221:
3805:
3122:
and alternative methods were described by other authors. In 2012, Vazirani offered a new simplified proof of the Micali-Vazirani algorithm.
2756:
In many instances, however, the time taken by the algorithm may be even faster than this worst case analysis indicates. For instance, in the
2964:
1435:
3054:
599:
can be achieved to find maximum-cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and
Vazirani.
1193:, there must also exist an augmenting path. If no augmenting path can be found, an algorithm may safely terminate, since in this case
4273:
3335:
the graph: uDummy connected to all unmatched vertices in U and vDummy connected to all unmatched vertices in V. Now, if we run a
2232:
Each phase consists of a single breadth first search and a single depth-first search. Thus, a single phase may be implemented in
3130:/* G = U ∪ V ∪ {NIL} where U and V are the left and right sides of the bipartite graph and NIL is a special null vertex */
4003:
3697:
Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao (2006), "Matching algorithms are fast in sparse random graphs",
458:
3376:
2224:
The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.
152:
90:
43:
3057:
and then, when the matching created by this algorithm becomes close to optimum, switching to the
Hopcroft–Karp method.
4088:
Peterson, Paul A.; Loui, Michael C. (November 1988), "The general maximum matching algorithm of Micali and
Vazirani",
3759:
The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms
3395:
3325:
Execution on an example graph showing input graph and matching after intermediate iteration 1 and final iteration 2.
3979:(1973), "An exact estimate of an algorithm for finding a maximum flow, applied to the problem on representatives",
2623:
edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most
4268:
155:
as output — a set of as many edges as possible with the property that no two edges share an endpoint. It runs in
3357:
Also observe that the DFS does not visit the same vertex multiple times. This is thanks to the following lines:
1597:
4208:. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics.
2895:, the Hopcroft–Karp algorithm continues to have the best known worst-case performance, but for dense graphs (
1403:
965:
must form a collection of disjoint cycles, of paths with an equal number of matched and unmatched edges in
4190:
4099:
3706:
2898:
36:
2700:
2368:
546:
158:
3976:
3792:, Lecture Notes in Computer Science, vol. 3895, Berlin and Heidelberg: Springer, pp. 218–240,
2757:
438:
3073:
464:
258:
4246:
3386:
3336:
2494:
1752:
1305:
1221:
710:
607:
603:
53:
4104:
3711:
2828:
2663:
2157:
running time for the DFS. It is also possible to work in the other direction, from free vertices in
367:
4195:
3776:
3747:, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia
3390:
2626:
2592:
2538:
2504:
2462:
2428:
2274:
821:
446:
1376:
1330:
317:
4236:
4159:
4125:
4076:
3932:
3895:
3869:
3845:
3732:
3686:
3660:
3547:
3382:
3347:
2783:
2015:
716:
4217:
4117:
3801:
3543:
453:, the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding
4209:
4149:
4109:
4068:
3964:
3922:
3879:
3827:
3793:
3716:
3670:
3639:
2235:
2121:
507:
132:
93:
3972:. Previously announced at the 12th Annual Symposium on Switching and Automata Theory, 1971.
3891:
3841:
3728:
3682:
1149:
1082:
1035:
1008:
901:
854:
742:
3906:
3887:
3857:
3837:
3724:
3678:
3568:; Paul, M. (1991), "Computing a maximum cardinality matching in a bipartite graph in time
2569:
paths in the collection, and the size of the optimal matching can differ from the size of
2459:
phases of the algorithm are complete, the shortest remaining augmenting path has at least
1217:
148:
100:
46:
3784:
2338:
2308:
775:. Thus, by finding augmenting paths, an algorithm may increase the size of the matching.
4250:
4137:
3997:
3772:
3771:
Dinitz, Yefim (2006), "Dinitz' Algorithm: The
Original Version and Even's Version", in
3551:
2776:) showed that with high probability all non-optimal matchings have augmenting paths of
2572:
2203:
2180:
2160:
2101:
2081:
2061:
2041:
2021:
1989:
1962:
1942:
1922:
1902:
1882:
1859:
1839:
1819:
1799:
1778:
1758:
1730:
1710:
1690:
1670:
1650:
1630:
1287:
1267:
1247:
1227:
1196:
1176:
1129:
1109:
1062:
988:
968:
948:
928:
881:
801:
781:
692:
672:
652:
621:
238:
218:
4262:
3993:
3944:
3910:
3651:
Annamalai, Chidambaram (2018), "Finding perfect matchings in bipartite hypergraphs",
3643:
3565:
3379:, the problem solved by the algorithm, and its generalization to non-bipartite graphs
426:
4080:
3936:
3849:
4233:
An
Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm
4163:
4090:
3948:
3815:
3736:
3690:
3321:
2892:
2765:
2761:
430:
361:
4140:(1994), "Average-case analysis of algorithms for matchings and related problems",
3989:. Previously announced at the Seminar on Combinatorial Mathematics (Moscow, 1971).
3899:
4129:
3780:
311:
4187:
Sequential and parallel experimental results with bipartite matching algorithms
2010:
means that no more such paths can be added. This is different from finding the
1836:
only matched edges may be traversed. The search terminates at the first layer
3720:
3674:
2780:
length. As a consequence, for these graphs, the
Hopcroft–Karp algorithm takes
1747:. The algorithm is run in phases. Each phase consists of the following steps.
1317:
212:
4121:
3623:{\displaystyle \scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}
4213:
4171:
Setubal, João C. (1993), "New experimental results for bipartite matching",
2777:
144:
3832:
4154:
3927:
3860:(2017), "The weighted matching approach to maximum cardinality matching",
3238:
Pair_V := u Pair_U := v
1581:{\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}
4072:
3913:(1991), "Faster scaling algorithms for general graph matching problems",
3883:
3398:
for finding maximum flow, a generalization of the
Hopcroft–Karp algorithm
2098:
at the current point in the DFS, then that vertex can't be used to reach
3797:
4113:
1755:
partitions the vertices of the graph into layers. The free vertices in
3046:{\displaystyle O\left(|V|^{1.5}{\sqrt {\frac {|E|}{\log |V|}}}\right)}
618:
A vertex that is not the endpoint of an edge in some partial matching
3745:
A faster implementation of a bipartite cardinality matching algorithm
1500:{\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}
3968:
3481:, section 12.3, bipartite cardinality matching problem, pp. 469–470.
1106:, so this difference is equal to the number of augmenting paths for
3874:
3665:
1216:
An augmenting path in a matching problem is closely related to the
4241:
3320:
3194:
Dist] := Dist + 1 Enqueue(Q, Pair_V)
1816:, only unmatched edges may be traversed, while from a vertex in
642:. The basic concept that the algorithm relies on is that of an
4189:, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas,
3786:
Theoretical Computer Science: Essays in Memory of Shimon Even
2497:
of the eventual optimal matching and of the partial matching
602:
The Hopcroft–Karp algorithm can be seen as a special case of
2200:
Every one of the paths found in this way is used to enlarge
1603:
1441:
4061:
algorithm for finding maximum matching in general graphs",
3430:
2769:
925:
are both matchings, every vertex has degree at most 2 in
1508:
maximal set of vertex-disjoint shortest augmenting paths
255:
is set of vertices of the graph, and it is assumed that
4175:, Dept. of Informatics, Univ. of Pisa, pp. 211–216
4054:{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}
4007:
3955:
algorithm for maximum matchings in bipartite graphs",
3575:
4064:
Proc. 21st IEEE Symp. Foundations of Computer Science
4006:
3574:
3076:
2967:
2901:
2831:
2786:
2703:
2666:
2629:
2595:
2575:
2541:
2507:
2465:
2431:
2371:
2341:
2311:
2277:
2238:
2206:
2183:
2163:
2124:
2104:
2084:
2064:
2044:
2024:
1992:
1965:
1945:
1925:
1905:
1885:
1862:
1842:
1822:
1802:
1781:
1761:
1733:
1713:
1693:
1673:
1653:
1633:
1600:
1517:
1438:
1406:
1379:
1333:
1290:
1270:
1250:
1230:
1199:
1179:
1152:
1132:
1112:
1085:
1065:
1038:
1011:
991:
971:
951:
931:
904:
884:
857:
824:
804:
784:
745:
719:
695:
675:
655:
624:
549:
510:
467:
370:
320:
261:
241:
221:
161:
103:
56:
2958:
2887:
Comparison with other bipartite matching algorithms
2657:additional phases before the algorithm terminates.
445:). As in previous methods for matching such as the
89:
42:
32:
24:
4053:
3622:
3556:Network Flows: Theory, Algorithms and Applications
3478:
3105:
3061:augmenting paths, and by push-relabel techniques.
3045:
2949:
2875:
2817:
2745:
2689:
2649:
2615:
2581:
2561:
2527:
2485:
2451:
2413:
2357:
2327:
2297:
2263:
2212:
2189:
2169:
2149:
2110:
2090:
2070:
2050:
2030:
1998:
1979:if and only if it ends a shortest augmenting path.
1971:
1951:
1931:
1911:
1891:
1868:
1848:
1828:
1808:
1787:
1767:
1739:
1719:
1699:
1679:
1659:
1639:
1616:
1580:
1499:
1418:
1391:
1360:
1296:
1276:
1256:
1236:
1205:
1185:
1165:
1138:
1118:
1098:
1071:
1051:
1024:
997:
977:
957:
937:
917:
890:
870:
843:
810:
790:
767:
731:
701:
681:
661:
630:
591:
535:
496:
414:
352:
302:
247:
227:
203:
118:
78:
3156:Dist := 0 Enqueue(Q, u)
2660:Since the algorithm performs a total of at most
1316:The algorithm may be expressed in the following
3743:Chang, S. Frank; McCormick, S. Thomas (1990),
3490:
3281:Pair_V := NIL matching := 0
3114:
2197:, which is the variant used in the pseudocode.
8:
3494:
3454:
3119:
2118:at any other point in the DFS. This ensures
1494:
1449:
434:
19:
3514:
16:Algorithm for maximum cardinality matching
4240:
4194:
4153:
4103:
4042:
4034:
4024:
4016:
4014:
4005:
3926:
3873:
3831:
3710:
3664:
3594:
3588:
3573:
3419:
3093:
3085:
3083:
3075:
3029:
3021:
3008:
3000:
2996:
2990:
2985:
2976:
2966:
2938:
2933:
2924:
2910:
2902:
2900:
2865:
2857:
2846:
2838:
2830:
2807:
2799:
2785:
2733:
2725:
2723:
2718:
2710:
2702:
2680:
2672:
2670:
2665:
2640:
2632:
2630:
2628:
2606:
2598:
2596:
2594:
2574:
2552:
2544:
2542:
2540:
2518:
2510:
2508:
2506:
2476:
2468:
2466:
2464:
2442:
2434:
2432:
2430:
2401:
2393:
2391:
2386:
2378:
2370:
2350:
2342:
2340:
2320:
2312:
2310:
2288:
2280:
2278:
2276:
2253:
2245:
2237:
2205:
2182:
2162:
2139:
2131:
2123:
2103:
2083:
2063:
2043:
2023:
1991:
1964:
1944:
1924:
1904:
1884:
1861:
1841:
1821:
1801:
1780:
1760:
1732:
1712:
1692:
1672:
1652:
1632:
1617:{\displaystyle {\mathcal {P}}=\emptyset }
1602:
1601:
1599:
1569:
1550:
1537:
1516:
1488:
1469:
1456:
1440:
1439:
1437:
1405:
1378:
1332:
1289:
1269:
1249:
1229:
1198:
1178:
1157:
1151:
1146:. Thus, whenever there exists a matching
1131:
1111:
1090:
1084:
1064:
1043:
1037:
1016:
1010:
990:
970:
950:
930:
909:
903:
883:
862:
856:
835:
823:
803:
783:
754:
746:
744:
718:
694:
674:
654:
623:
579:
571:
569:
564:
556:
548:
525:
517:
509:
484:
476:
474:
466:
404:
396:
385:
377:
369:
341:
336:
327:
319:
292:
284:
270:
262:
260:
240:
220:
191:
183:
181:
176:
168:
160:
102:
66:
55:
3526:
442:
4178:
3764:
3750:
3502:
3498:
3408:
2961:achieves a slightly better time bound,
2773:
1032:; but the latter is impossible because
450:
4206:Data Structures and Network Algorithms
3466:
3442:
3385:, a generalization of this problem on
3160:Dist := ∞ Dist := ∞
3053:. Their algorithm is based on using a
1727:at any time be represented as the set
1667:be the two sets in the bipartition of
1419:{\displaystyle M\leftarrow \emptyset }
139:(sometimes more accurately called the
18:
3415:
1982:The algorithm finds a maximal set of
7:
3818:(1965), "Paths, Trees and Flowers",
3242:true Dist := ∞
2950:{\displaystyle |E|=\Omega (|V|^{2})}
778:Conversely, suppose that a matching
543:iterations. The same performance of
3055:push-relabel maximum flow algorithm
2746:{\displaystyle O(|E|{\sqrt {|V|}})}
2414:{\displaystyle O(|E|{\sqrt {|V|}})}
1856:where one or more free vertices in
592:{\displaystyle O(|E|{\sqrt {|V|}})}
204:{\displaystyle O(|E|{\sqrt {|V|}})}
3479:Ahuja, Magnanti & Orlin (1993)
3314:matching := matching + 1
2918:
1611:
1413:
739:, would form a matching with size
689:is an augmenting path relative to
278:
14:
3761:, Ph.D. thesis, Brunel University
2697:phases, it takes a total time of
1173:larger than the current matching
504:iterations are needed instead of
3106:{\displaystyle O({\sqrt {|V|}})}
2772:(improving a previous result of
1264:to the sink; and let edges from
878:is an optimal matching. Because
497:{\displaystyle O({\sqrt {|V|}})}
425:The algorithm was discovered by
303:{\displaystyle |E|=\Omega (|V|)}
141:Hopcroft–Karp–Karzanov algorithm
3820:Canadian Journal of Mathematics
79:{\displaystyle O(E{\sqrt {V}})}
4047:
4043:
4035:
4025:
4017:
4011:
3757:Darby-Dowman, Kenneth (1980),
3632:Information Processing Letters
3100:
3094:
3086:
3080:
3030:
3022:
3009:
3001:
2986:
2977:
2944:
2934:
2925:
2921:
2911:
2903:
2876:{\displaystyle O(|E|\log |V|)}
2870:
2866:
2858:
2847:
2839:
2835:
2812:
2808:
2800:
2790:
2740:
2734:
2726:
2719:
2711:
2707:
2690:{\displaystyle 2{\sqrt {|V|}}}
2681:
2673:
2641:
2633:
2607:
2599:
2553:
2545:
2519:
2511:
2477:
2469:
2443:
2435:
2408:
2402:
2394:
2387:
2379:
2375:
2351:
2343:
2321:
2313:
2289:
2281:
2258:
2254:
2246:
2242:
2144:
2140:
2132:
2128:
1575:
1530:
1521:
1446:
1410:
1355:
1337:
1005:, and of augmenting paths for
755:
747:
586:
580:
572:
565:
557:
553:
530:
526:
518:
514:
491:
485:
477:
471:
415:{\displaystyle O(|E|\log |V|)}
409:
405:
397:
386:
378:
374:
347:
337:
328:
324:
297:
293:
285:
281:
271:
263:
235:is set of edges in the graph,
198:
192:
184:
177:
169:
165:
113:
107:
73:
60:
1:
4204:Tarjan, Robert Endre (1983).
3168:u := Dequeue(Q)
3118:exposition" was published by
2957:) a more recent algorithm by
2650:{\displaystyle {\sqrt {|V|}}}
2616:{\displaystyle {\sqrt {|V|}}}
2562:{\displaystyle {\sqrt {|V|}}}
2528:{\displaystyle {\sqrt {|V|}}}
2486:{\displaystyle {\sqrt {|V|}}}
2452:{\displaystyle {\sqrt {|V|}}}
2298:{\displaystyle {\sqrt {|V|}}}
844:{\displaystyle M\oplus M^{*}}
3644:10.1016/0020-0190(91)90195-N
3491:Chang & McCormick (1990)
3377:Maximum cardinality matching
3115:Micali & Vazirani (1980)
1687:, and let the matching from
1392:{\displaystyle M\subseteq E}
1361:{\displaystyle G(U\cup V,E)}
818:be the symmetric difference
353:{\displaystyle O(|V|^{2.5})}
153:maximum-cardinality matching
3699:Theory of Computing Systems
2818:{\displaystyle O(\log |V|)}
2271:time. Therefore, the first
1986:augmenting paths of length
4290:
3455:Peterson & Loui (1988)
3120:Peterson & Loui (1988)
2493:edges in it. However, the
1244:, and from each vertex in
985:, of augmenting paths for
713:of the two sets of edges,
4185:Setubal, João C. (1996),
3957:SIAM Journal on Computing
3721:10.1007/s00224-005-1254-y
3675:10.1007/s00493-017-3567-2
3515:Gabow & Tarjan (1991)
1919:are collected into a set
732:{\displaystyle M\oplus P}
151:as input and produces a
4231:Vazirani, Vijay (2012),
2305:phases, in a graph with
2038:to the free vertices in
798:is not optimal, and let
459:Ford–Fulkerson algorithm
4274:Matching (graph theory)
4214:10.1137/1.9781611970265
3981:Problems in Cybernetics
3862:Fundamenta Informaticae
3269:Pair_U := NIL
2535:, there can be at most
437:) and independently by
422:with high probability.
314:the time bound becomes
137:Hopcroft–Karp algorithm
20:Hopcroft–Karp algorithm
4235:, CoRR abs/1210.4594,
4055:
3833:10.4153/CJM-1965-045-4
3624:
3396:Edmonds–Karp algorithm
3360:Dist = ∞ return false
3326:
3107:
3047:
2951:
2877:
2819:
2747:
2691:
2651:
2617:
2583:
2563:
2529:
2487:
2453:
2415:
2359:
2329:
2299:
2265:
2264:{\displaystyle O(|E|)}
2214:
2191:
2171:
2151:
2150:{\displaystyle O(|E|)}
2112:
2092:
2072:
2052:
2032:
2000:
1973:
1953:
1933:
1913:
1893:
1870:
1850:
1830:
1810:
1789:
1769:
1741:
1721:
1701:
1681:
1661:
1641:
1618:
1582:
1501:
1420:
1393:
1362:
1298:
1278:
1258:
1238:
1207:
1187:
1167:
1140:
1120:
1100:
1073:
1053:
1026:
999:
979:
959:
939:
919:
892:
872:
845:
812:
792:
769:
733:
703:
683:
663:
632:
593:
537:
536:{\displaystyle O(|V|)}
498:
439:Alexander Karzanov
416:
354:
304:
249:
229:
205:
120:
80:
4155:10.1145/195613.195663
4056:
3928:10.1145/115234.115366
3625:
3389:, solved e.g. by the
3324:
3108:
3048:
2952:
2878:
2820:
2748:
2692:
2652:
2618:
2584:
2564:
2530:
2488:
2454:
2416:
2360:
2330:
2300:
2266:
2215:
2192:
2172:
2152:
2113:
2093:
2073:
2053:
2033:
2001:
1974:
1954:
1934:
1914:
1894:
1879:All free vertices in
1871:
1851:
1831:
1811:
1790:
1770:
1742:
1722:
1702:
1682:
1662:
1642:
1619:
1583:
1502:
1421:
1394:
1363:
1299:
1279:
1259:
1239:
1222:maximum flow problems
1208:
1188:
1168:
1166:{\displaystyle M^{*}}
1141:
1121:
1101:
1099:{\displaystyle M^{*}}
1074:
1054:
1052:{\displaystyle M^{*}}
1027:
1025:{\displaystyle M^{*}}
1000:
980:
960:
940:
920:
918:{\displaystyle M^{*}}
893:
873:
871:{\displaystyle M^{*}}
846:
813:
793:
770:
768:{\displaystyle |M|+1}
734:
704:
684:
664:
633:
594:
538:
499:
417:
355:
305:
250:
230:
206:
121:
81:
4073:10.1109/SFCS.1980.12
4004:
3884:10.3233/FI-2017-1555
3777:Rosenberg, Arnold L.
3572:
3337:breadth-first search
3074:
3065:Non-bipartite graphs
2965:
2899:
2829:
2784:
2701:
2664:
2627:
2593:
2573:
2539:
2505:
2495:symmetric difference
2463:
2429:
2369:
2339:
2309:
2275:
2236:
2204:
2181:
2161:
2122:
2102:
2082:
2062:
2042:
2022:
1990:
1963:
1943:
1939:. That is, a vertex
1923:
1903:
1883:
1860:
1840:
1820:
1800:
1779:
1759:
1753:breadth-first search
1731:
1711:
1691:
1671:
1651:
1631:
1627:In more detail, let
1598:
1515:
1436:
1404:
1377:
1331:
1288:
1268:
1248:
1228:
1197:
1177:
1150:
1130:
1110:
1083:
1063:
1036:
1009:
989:
969:
949:
929:
902:
882:
855:
822:
802:
782:
743:
717:
711:symmetric difference
693:
673:
653:
622:
608:maximum-flow problem
547:
508:
465:
368:
318:
259:
239:
219:
159:
119:{\displaystyle O(V)}
101:
54:
4251:2012arXiv1210.4594V
3798:10.1007/11685654_10
3564:Alt, H.; Blum, N.;
3548:Magnanti, Thomas L.
3495:Darby-Dowman (1980)
3391:Hungarian algorithm
3234:DFS(Pair_V) = true
2753:in the worst case.
2358:{\displaystyle |E|}
2328:{\displaystyle |V|}
669:is a matching, and
447:Hungarian algorithm
21:
4142:Journal of the ACM
4114:10.1007/BF01762129
4067:, pp. 17–27,
4051:
4050:
3915:Journal of the ACM
3620:
3619:
3544:Ahuja, Ravindra K.
3431:Bast et al. (2006)
3383:Assignment problem
3348:depth-first search
3327:
3103:
3043:
2947:
2873:
2815:
2770:Bast et al. (2006)
2743:
2687:
2647:
2613:
2579:
2559:
2525:
2483:
2449:
2411:
2355:
2325:
2295:
2261:
2210:
2187:
2167:
2147:
2108:
2088:
2068:
2048:
2028:
2016:depth-first search
1996:
1969:
1949:
1929:
1909:
1889:
1866:
1846:
1826:
1806:
1785:
1765:
1737:
1717:
1697:
1677:
1657:
1637:
1614:
1578:
1497:
1416:
1389:
1358:
1327:: Bipartite graph
1294:
1274:
1254:
1234:
1203:
1183:
1163:
1136:
1116:
1096:
1069:
1049:
1022:
995:
975:
955:
935:
915:
888:
868:
841:
808:
788:
765:
729:
699:
679:
659:
628:
589:
533:
494:
412:
350:
300:
245:
225:
201:
116:
76:
4223:978-0-89871-187-5
4029:
3945:Hopcroft, John E.
3911:Tarjan, Robert E.
3807:978-3-540-32880-3
3612:
3611:
3227:Dist] = Dist + 1
3164:Empty(Q) = false
3098:
3036:
3035:
2959:Alt et al. (1991)
2738:
2685:
2645:
2611:
2582:{\displaystyle M}
2557:
2523:
2481:
2447:
2406:
2365:edges, take time
2293:
2213:{\displaystyle M}
2190:{\displaystyle V}
2170:{\displaystyle U}
2111:{\displaystyle U}
2091:{\displaystyle U}
2071:{\displaystyle F}
2051:{\displaystyle U}
2031:{\displaystyle F}
1999:{\displaystyle k}
1972:{\displaystyle F}
1952:{\displaystyle v}
1932:{\displaystyle F}
1912:{\displaystyle k}
1892:{\displaystyle V}
1869:{\displaystyle V}
1849:{\displaystyle k}
1829:{\displaystyle V}
1809:{\displaystyle U}
1788:{\displaystyle U}
1768:{\displaystyle U}
1740:{\displaystyle M}
1720:{\displaystyle V}
1700:{\displaystyle U}
1680:{\displaystyle G}
1660:{\displaystyle V}
1640:{\displaystyle U}
1306:Dinic's algorithm
1297:{\displaystyle V}
1277:{\displaystyle U}
1257:{\displaystyle V}
1237:{\displaystyle U}
1213:must be optimal.
1206:{\displaystyle M}
1186:{\displaystyle M}
1139:{\displaystyle P}
1119:{\displaystyle M}
1072:{\displaystyle M}
998:{\displaystyle M}
978:{\displaystyle M}
958:{\displaystyle P}
938:{\displaystyle P}
891:{\displaystyle M}
811:{\displaystyle P}
791:{\displaystyle M}
702:{\displaystyle M}
682:{\displaystyle P}
662:{\displaystyle M}
631:{\displaystyle M}
604:Dinic's algorithm
584:
489:
427:John Hopcroft
360:, and for sparse
310:. In the case of
248:{\displaystyle V}
228:{\displaystyle E}
196:
129:
128:
71:
4281:
4269:Graph algorithms
4253:
4244:
4227:
4199:
4198:
4176:
4166:
4157:
4148:(6): 1329–1356,
4132:
4107:
4098:(1–4): 511–533,
4083:
4060:
4058:
4057:
4052:
4046:
4038:
4030:
4028:
4020:
4015:
3988:
3971:
3949:Karp, Richard M.
3939:
3930:
3907:Gabow, Harold N.
3902:
3877:
3868:(1–4): 109–130,
3858:Gabow, Harold N.
3852:
3835:
3810:
3791:
3762:
3748:
3739:
3714:
3693:
3668:
3659:(6): 1285–1307,
3646:
3629:
3627:
3626:
3621:
3618:
3614:
3613:
3610:
3596:
3595:
3593:
3592:
3559:
3529:
3524:
3518:
3512:
3506:
3488:
3482:
3476:
3470:
3464:
3458:
3452:
3446:
3440:
3434:
3428:
3422:
3420:Annamalai (2018)
3413:
3112:
3110:
3109:
3104:
3099:
3097:
3089:
3084:
3052:
3050:
3049:
3044:
3042:
3038:
3037:
3034:
3033:
3025:
3013:
3012:
3004:
2998:
2997:
2995:
2994:
2989:
2980:
2956:
2954:
2953:
2948:
2943:
2942:
2937:
2928:
2914:
2906:
2882:
2880:
2879:
2874:
2869:
2861:
2850:
2842:
2824:
2822:
2821:
2816:
2811:
2803:
2752:
2750:
2749:
2744:
2739:
2737:
2729:
2724:
2722:
2714:
2696:
2694:
2693:
2688:
2686:
2684:
2676:
2671:
2656:
2654:
2653:
2648:
2646:
2644:
2636:
2631:
2622:
2620:
2619:
2614:
2612:
2610:
2602:
2597:
2588:
2586:
2585:
2580:
2568:
2566:
2565:
2560:
2558:
2556:
2548:
2543:
2534:
2532:
2531:
2526:
2524:
2522:
2514:
2509:
2492:
2490:
2489:
2484:
2482:
2480:
2472:
2467:
2458:
2456:
2455:
2450:
2448:
2446:
2438:
2433:
2420:
2418:
2417:
2412:
2407:
2405:
2397:
2392:
2390:
2382:
2364:
2362:
2361:
2356:
2354:
2346:
2334:
2332:
2331:
2326:
2324:
2316:
2304:
2302:
2301:
2296:
2294:
2292:
2284:
2279:
2270:
2268:
2267:
2262:
2257:
2249:
2219:
2217:
2216:
2211:
2196:
2194:
2193:
2188:
2176:
2174:
2173:
2168:
2156:
2154:
2153:
2148:
2143:
2135:
2117:
2115:
2114:
2109:
2097:
2095:
2094:
2089:
2077:
2075:
2074:
2069:
2057:
2055:
2054:
2049:
2037:
2035:
2034:
2029:
2005:
2003:
2002:
1997:
1978:
1976:
1975:
1970:
1958:
1956:
1955:
1950:
1938:
1936:
1935:
1930:
1918:
1916:
1915:
1910:
1898:
1896:
1895:
1890:
1875:
1873:
1872:
1867:
1855:
1853:
1852:
1847:
1835:
1833:
1832:
1827:
1815:
1813:
1812:
1807:
1794:
1792:
1791:
1786:
1774:
1772:
1771:
1766:
1746:
1744:
1743:
1738:
1726:
1724:
1723:
1718:
1706:
1704:
1703:
1698:
1686:
1684:
1683:
1678:
1666:
1664:
1663:
1658:
1646:
1644:
1643:
1638:
1623:
1621:
1620:
1615:
1607:
1606:
1587:
1585:
1584:
1579:
1574:
1573:
1555:
1554:
1542:
1541:
1506:
1504:
1503:
1498:
1493:
1492:
1474:
1473:
1461:
1460:
1445:
1444:
1425:
1423:
1422:
1417:
1398:
1396:
1395:
1390:
1367:
1365:
1364:
1359:
1303:
1301:
1300:
1295:
1283:
1281:
1280:
1275:
1263:
1261:
1260:
1255:
1243:
1241:
1240:
1235:
1218:augmenting paths
1212:
1210:
1209:
1204:
1192:
1190:
1189:
1184:
1172:
1170:
1169:
1164:
1162:
1161:
1145:
1143:
1142:
1137:
1125:
1123:
1122:
1117:
1105:
1103:
1102:
1097:
1095:
1094:
1078:
1076:
1075:
1070:
1058:
1056:
1055:
1050:
1048:
1047:
1031:
1029:
1028:
1023:
1021:
1020:
1004:
1002:
1001:
996:
984:
982:
981:
976:
964:
962:
961:
956:
944:
942:
941:
936:
924:
922:
921:
916:
914:
913:
897:
895:
894:
889:
877:
875:
874:
869:
867:
866:
850:
848:
847:
842:
840:
839:
817:
815:
814:
809:
797:
795:
794:
789:
774:
772:
771:
766:
758:
750:
738:
736:
735:
730:
708:
706:
705:
700:
688:
686:
685:
680:
668:
666:
665:
660:
637:
635:
634:
629:
614:Augmenting paths
598:
596:
595:
590:
585:
583:
575:
570:
568:
560:
542:
540:
539:
534:
529:
521:
503:
501:
500:
495:
490:
488:
480:
475:
455:augmenting paths
449:and the work of
421:
419:
418:
413:
408:
400:
389:
381:
364:it runs in time
359:
357:
356:
351:
346:
345:
340:
331:
309:
307:
306:
301:
296:
288:
274:
266:
254:
252:
251:
246:
234:
232:
231:
226:
210:
208:
207:
202:
197:
195:
187:
182:
180:
172:
133:computer science
125:
123:
122:
117:
94:space complexity
85:
83:
82:
77:
72:
67:
22:
4289:
4288:
4284:
4283:
4282:
4280:
4279:
4278:
4259:
4258:
4257:
4230:
4224:
4203:
4184:
4173:Proc. Netflow93
4170:
4138:Motwani, Rajeev
4136:
4105:10.1.1.228.9625
4087:
4002:
4001:
3998:Vazirani, V. V.
3992:
3977:Karzanov, A. V.
3975:
3969:10.1137/0202019
3943:
3905:
3856:
3814:
3808:
3789:
3781:Selman, Alan L.
3773:Goldreich, Oded
3770:
3756:
3742:
3712:10.1.1.395.6643
3696:
3650:
3600:
3584:
3583:
3579:
3570:
3569:
3563:
3558:, Prentice-Hall
3552:Orlin, James B.
3542:
3538:
3533:
3532:
3527:Vazirani (2012)
3525:
3521:
3513:
3509:
3489:
3485:
3477:
3473:
3465:
3461:
3453:
3449:
3441:
3437:
3429:
3425:
3414:
3410:
3405:
3387:weighted graphs
3373:
3361:
3332:
3319:
3172:Dist < Dist
3128:
3072:
3071:
3067:
3014:
2999:
2984:
2975:
2971:
2963:
2962:
2932:
2897:
2896:
2889:
2827:
2826:
2782:
2781:
2699:
2698:
2662:
2661:
2625:
2624:
2591:
2590:
2571:
2570:
2537:
2536:
2503:
2502:
2461:
2460:
2427:
2426:
2367:
2366:
2337:
2336:
2307:
2306:
2273:
2272:
2234:
2233:
2230:
2202:
2201:
2179:
2178:
2159:
2158:
2120:
2119:
2100:
2099:
2080:
2079:
2060:
2059:
2040:
2039:
2020:
2019:
1988:
1987:
1984:vertex disjoint
1961:
1960:
1941:
1940:
1921:
1920:
1901:
1900:
1881:
1880:
1858:
1857:
1838:
1837:
1818:
1817:
1798:
1797:
1777:
1776:
1757:
1756:
1729:
1728:
1709:
1708:
1689:
1688:
1669:
1668:
1649:
1648:
1629:
1628:
1596:
1595:
1565:
1546:
1533:
1513:
1512:
1484:
1465:
1452:
1434:
1433:
1402:
1401:
1375:
1374:
1329:
1328:
1314:
1286:
1285:
1266:
1265:
1246:
1245:
1226:
1225:
1195:
1194:
1175:
1174:
1153:
1148:
1147:
1128:
1127:
1108:
1107:
1086:
1081:
1080:
1061:
1060:
1039:
1034:
1033:
1012:
1007:
1006:
987:
986:
967:
966:
947:
946:
927:
926:
905:
900:
899:
880:
879:
858:
853:
852:
831:
820:
819:
800:
799:
780:
779:
741:
740:
715:
714:
691:
690:
671:
670:
651:
650:
644:augmenting path
620:
619:
616:
545:
544:
506:
505:
463:
462:
366:
365:
335:
316:
315:
257:
256:
237:
236:
217:
216:
157:
156:
149:bipartite graph
99:
98:
52:
51:
28:Graph algorithm
17:
12:
11:
5:
4287:
4285:
4277:
4276:
4271:
4261:
4260:
4256:
4255:
4228:
4222:
4201:
4196:10.1.1.48.3539
4182:
4179:Setubal (1996)
4177:. As cited by
4168:
4134:
4085:
4049:
4045:
4041:
4037:
4033:
4027:
4023:
4019:
4013:
4010:
3990:
3973:
3963:(4): 225–231,
3941:
3921:(4): 815–853,
3903:
3854:
3812:
3806:
3768:
3765:Setubal (1996)
3763:. As cited by
3754:
3751:Setubal (1996)
3749:. As cited by
3740:
3694:
3648:
3638:(4): 237–240,
3617:
3609:
3606:
3603:
3599:
3591:
3587:
3582:
3578:
3561:
3539:
3537:
3534:
3531:
3530:
3519:
3507:
3503:Setubal (1996)
3499:Setubal (1993)
3483:
3471:
3469:, p. 102.
3459:
3447:
3435:
3423:
3407:
3406:
3404:
3401:
3400:
3399:
3393:
3380:
3372:
3369:
3359:
3331:
3328:
3310:DFS(u) = true
3254:Hopcroft–Karp
3129:
3127:
3124:
3102:
3096:
3092:
3088:
3082:
3079:
3066:
3063:
3041:
3032:
3028:
3024:
3020:
3017:
3011:
3007:
3003:
2993:
2988:
2983:
2979:
2974:
2970:
2946:
2941:
2936:
2931:
2927:
2923:
2920:
2917:
2913:
2909:
2905:
2888:
2885:
2872:
2868:
2864:
2860:
2856:
2853:
2849:
2845:
2841:
2837:
2834:
2814:
2810:
2806:
2802:
2798:
2795:
2792:
2789:
2742:
2736:
2732:
2728:
2721:
2717:
2713:
2709:
2706:
2683:
2679:
2675:
2669:
2643:
2639:
2635:
2609:
2605:
2601:
2578:
2555:
2551:
2547:
2521:
2517:
2513:
2479:
2475:
2471:
2445:
2441:
2437:
2410:
2404:
2400:
2396:
2389:
2385:
2381:
2377:
2374:
2353:
2349:
2345:
2323:
2319:
2315:
2291:
2287:
2283:
2260:
2256:
2252:
2248:
2244:
2241:
2229:
2226:
2222:
2221:
2209:
2198:
2186:
2166:
2146:
2142:
2138:
2134:
2130:
2127:
2107:
2087:
2067:
2047:
2027:
1995:
1980:
1968:
1948:
1928:
1908:
1888:
1877:
1865:
1845:
1825:
1805:
1784:
1764:
1736:
1716:
1696:
1676:
1656:
1636:
1625:
1624:
1613:
1610:
1605:
1590:
1589:
1588:
1577:
1572:
1568:
1564:
1561:
1558:
1553:
1549:
1545:
1540:
1536:
1532:
1529:
1526:
1523:
1520:
1510:
1496:
1491:
1487:
1483:
1480:
1477:
1472:
1468:
1464:
1459:
1455:
1451:
1448:
1443:
1426:
1415:
1412:
1409:
1399:
1388:
1385:
1382:
1368:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1313:
1310:
1293:
1273:
1253:
1233:
1202:
1182:
1160:
1156:
1135:
1115:
1093:
1089:
1068:
1046:
1042:
1019:
1015:
994:
974:
954:
934:
912:
908:
887:
865:
861:
838:
834:
830:
827:
807:
787:
764:
761:
757:
753:
749:
728:
725:
722:
698:
678:
658:
627:
615:
612:
588:
582:
578:
574:
567:
563:
559:
555:
552:
532:
528:
524:
520:
516:
513:
493:
487:
483:
479:
473:
470:
451:Edmonds (1965)
411:
407:
403:
399:
395:
392:
388:
384:
380:
376:
373:
349:
344:
339:
334:
330:
326:
323:
299:
295:
291:
287:
283:
280:
277:
273:
269:
265:
244:
224:
200:
194:
190:
186:
179:
175:
171:
167:
164:
127:
126:
115:
112:
109:
106:
96:
87:
86:
75:
70:
65:
62:
59:
49:
40:
39:
34:
33:Data structure
30:
29:
26:
15:
13:
10:
9:
6:
4:
3:
2:
4286:
4275:
4272:
4270:
4267:
4266:
4264:
4252:
4248:
4243:
4238:
4234:
4229:
4225:
4219:
4215:
4211:
4207:
4202:
4197:
4192:
4188:
4183:
4180:
4174:
4169:
4165:
4161:
4156:
4151:
4147:
4143:
4139:
4135:
4131:
4127:
4123:
4119:
4115:
4111:
4106:
4101:
4097:
4093:
4092:
4086:
4082:
4078:
4074:
4070:
4066:
4065:
4039:
4031:
4021:
4008:
3999:
3995:
3991:
3986:
3982:
3978:
3974:
3970:
3966:
3962:
3958:
3954:
3950:
3946:
3942:
3938:
3934:
3929:
3924:
3920:
3916:
3912:
3908:
3904:
3901:
3897:
3893:
3889:
3885:
3881:
3876:
3871:
3867:
3863:
3859:
3855:
3851:
3847:
3843:
3839:
3834:
3829:
3825:
3821:
3817:
3816:Edmonds, Jack
3813:
3809:
3803:
3799:
3795:
3788:
3787:
3782:
3778:
3774:
3769:
3766:
3760:
3755:
3752:
3746:
3741:
3738:
3734:
3730:
3726:
3722:
3718:
3713:
3708:
3704:
3700:
3695:
3692:
3688:
3684:
3680:
3676:
3672:
3667:
3662:
3658:
3654:
3653:Combinatorica
3649:
3645:
3641:
3637:
3633:
3615:
3607:
3604:
3601:
3597:
3589:
3585:
3580:
3576:
3567:
3562:
3557:
3553:
3549:
3545:
3541:
3540:
3535:
3528:
3523:
3520:
3516:
3511:
3508:
3504:
3500:
3496:
3492:
3487:
3484:
3480:
3475:
3472:
3468:
3467:Tarjan (1983)
3463:
3460:
3456:
3451:
3448:
3444:
3443:Dinitz (2006)
3439:
3436:
3432:
3427:
3424:
3421:
3417:
3412:
3409:
3402:
3397:
3394:
3392:
3388:
3384:
3381:
3378:
3375:
3374:
3370:
3368:
3364:
3358:
3355:
3351:
3349:
3344:
3340:
3338:
3329:
3323:
3317:
3313:
3309:
3306:
3303:Pair_U = NIL
3302:
3299:
3295:
3291:
3288:
3285:BFS() = true
3284:
3280:
3276:
3272:
3268:
3264:
3260:
3257:
3253:
3249:
3245:
3241:
3237:
3233:
3230:
3226:
3223:
3219:
3215:
3212:
3208:
3205:
3201:
3197:
3193:
3189:
3186:
3182:
3178:
3175:
3171:
3167:
3163:
3159:
3155:
3152:Pair_U = NIL
3151:
3148:
3144:
3140:
3137:
3133:
3125:
3123:
3121:
3116:
3090:
3077:
3064:
3062:
3058:
3056:
3039:
3026:
3018:
3015:
3005:
2991:
2981:
2972:
2968:
2960:
2939:
2929:
2915:
2907:
2894:
2893:sparse graphs
2886:
2884:
2862:
2854:
2851:
2843:
2832:
2804:
2796:
2793:
2787:
2779:
2775:
2771:
2767:
2766:random graphs
2763:
2759:
2754:
2730:
2715:
2704:
2677:
2667:
2658:
2637:
2603:
2576:
2549:
2515:
2500:
2496:
2473:
2439:
2422:
2398:
2383:
2372:
2347:
2335:vertices and
2317:
2285:
2250:
2239:
2227:
2225:
2207:
2199:
2184:
2164:
2136:
2125:
2105:
2085:
2065:
2045:
2025:
2017:
2013:
2009:
1993:
1985:
1981:
1966:
1946:
1926:
1906:
1886:
1878:
1863:
1843:
1823:
1803:
1782:
1762:
1754:
1750:
1749:
1748:
1734:
1714:
1694:
1674:
1654:
1634:
1608:
1594:
1591:
1570:
1566:
1562:
1559:
1556:
1551:
1547:
1543:
1538:
1534:
1527:
1524:
1518:
1511:
1509:
1489:
1485:
1481:
1478:
1475:
1470:
1466:
1462:
1457:
1453:
1432:
1431:
1430:
1427:
1407:
1400:
1386:
1383:
1380:
1372:
1369:
1352:
1349:
1346:
1343:
1340:
1334:
1326:
1323:
1322:
1321:
1319:
1311:
1309:
1307:
1291:
1271:
1251:
1231:
1223:
1219:
1214:
1200:
1180:
1158:
1154:
1133:
1113:
1091:
1087:
1066:
1044:
1040:
1017:
1013:
992:
972:
952:
932:
910:
906:
885:
863:
859:
836:
832:
828:
825:
805:
785:
776:
762:
759:
751:
726:
723:
720:
712:
696:
676:
656:
647:
645:
641:
625:
613:
611:
609:
605:
600:
576:
561:
550:
522:
511:
481:
468:
460:
456:
452:
448:
444:
440:
436:
432:
429: and
428:
423:
401:
393:
390:
382:
371:
363:
362:random graphs
342:
332:
321:
313:
289:
275:
267:
242:
222:
214:
188:
173:
162:
154:
150:
147:that takes a
146:
142:
138:
134:
110:
104:
97:
95:
92:
88:
68:
63:
57:
50:
48:
45:
41:
38:
35:
31:
27:
23:
4232:
4205:
4186:
4172:
4145:
4141:
4095:
4091:Algorithmica
4089:
4063:
4000:(1980), "An
3984:
3980:
3960:
3956:
3952:
3951:(1973), "An
3918:
3914:
3865:
3861:
3823:
3819:
3785:
3758:
3744:
3702:
3698:
3656:
3652:
3635:
3631:
3566:Mehlhorn, K.
3555:
3522:
3510:
3486:
3474:
3462:
3450:
3438:
3426:
3416:Gabow (2017)
3411:
3365:
3362:
3356:
3352:
3345:
3341:
3333:
3315:
3311:
3307:
3304:
3300:
3297:
3293:
3289:
3286:
3282:
3278:
3274:
3270:
3266:
3262:
3258:
3255:
3251:
3247:
3243:
3239:
3235:
3231:
3228:
3224:
3221:
3217:
3213:
3210:
3206:
3203:
3199:
3195:
3191:
3187:
3184:
3180:
3176:
3173:
3169:
3165:
3161:
3157:
3153:
3149:
3146:
3142:
3138:
3135:
3131:
3068:
3059:
2890:
2883:total time.
2774:Motwani 1994
2758:average case
2755:
2659:
2498:
2423:
2231:
2223:
2177:to those in
2011:
2007:
1983:
1959:is put into
1876:are reached.
1626:
1592:
1507:
1428:
1370:
1324:
1315:
1215:
777:
648:
643:
639:
638:is called a
617:
601:
454:
431:Richard Karp
424:
312:dense graphs
211:time in the
140:
136:
130:
3826:: 449–467,
3705:(1): 3–14,
3330:Explanation
2825:phases and
2778:logarithmic
2589:by at most
2018:(DFS) from
1373:: Matching
1220:arising in
709:, then the
640:free vertex
47:performance
4263:Categories
3994:Micali, S.
3875:1703.03998
3666:1509.07007
3536:References
3246:false
3190:Dist] = ∞
3126:Pseudocode
2764:bipartite
1318:pseudocode
213:worst case
91:Worst-case
44:Worst-case
4242:1210.4594
4191:CiteSeerX
4122:1432-0541
4100:CiteSeerX
4032:⋅
3707:CiteSeerX
3605:
3318:matching
3198:Dist ≠ ∞
3019:
2919:Ω
2855:
2797:
1899:at layer
1612:∅
1563:∪
1560:⋯
1557:∪
1544:∪
1528:⊕
1522:←
1479:…
1447:←
1414:∅
1411:←
1384:⊆
1344:∪
1312:Algorithm
1159:∗
1092:∗
1045:∗
1018:∗
911:∗
864:∗
837:∗
829:⊕
724:⊕
394:
279:Ω
145:algorithm
4081:27467816
3937:18350108
3850:18909734
3783:(eds.),
3554:(1993),
3371:See also
3290:for each
3271:for each
3259:for each
3252:function
3214:for each
3209:u ≠ NIL
3200:function
3177:for each
3139:for each
3132:function
2228:Analysis
606:for the
215:, where
143:) is an
4247:Bibcode
4164:2968208
3987:: 66–70
3892:3690573
3842:0177907
3737:9321036
3729:2189556
3691:1997334
3683:3910876
3202:DFS(u)
2012:maximum
2008:Maximal
441: (
433: (
4220:
4193:
4162:
4128:
4120:
4102:
4079:
3935:
3900:386509
3898:
3890:
3848:
3840:
3804:
3735:
3727:
3709:
3689:
3681:
3316:return
3248:return
3244:return
3240:return
3196:return
3134:BFS()
2762:sparse
1429:repeat
1371:Output
851:where
135:, the
4237:arXiv
4160:S2CID
4130:16820
4126:S2CID
4077:S2CID
3933:S2CID
3896:S2CID
3870:arXiv
3846:S2CID
3790:(PDF)
3733:S2CID
3687:S2CID
3661:arXiv
3403:Notes
3283:while
3250:true
3162:while
1593:until
1325:Input
945:. So
37:Graph
25:Class
4218:ISBN
4118:ISSN
3802:ISBN
3312:then
3305:then
3236:then
3229:then
3220:Adj
3211:then
3192:then
3183:Adj
3174:then
3158:else
3154:then
2891:For
2760:for
1647:and
1079:and
898:and
443:1973
435:1973
4210:doi
4150:doi
4110:doi
4069:doi
3965:doi
3923:doi
3880:doi
3866:154
3828:doi
3794:doi
3717:doi
3671:doi
3640:doi
3630:",
3602:log
3590:1.5
3016:log
2992:1.5
2852:log
2794:log
2006:. (
1707:to
1284:to
1126:in
649:If
391:log
343:2.5
131:In
4265::
4245:,
4216:.
4158:,
4146:41
4144:,
4124:,
4116:,
4108:,
4094:,
4075:,
3996:;
3983:,
3959:,
3947:;
3931:,
3919:38
3917:,
3909:;
3894:,
3888:MR
3886:,
3878:,
3864:,
3844:,
3838:MR
3836:,
3824:17
3822:,
3800:,
3779:;
3775:;
3731:,
3725:MR
3723:,
3715:,
3703:39
3701:,
3685:,
3679:MR
3677:,
3669:,
3657:38
3655:,
3636:37
3634:,
3550:;
3546:;
3501:;
3497:;
3493:;
3418:;
3308:if
3301:if
3298:do
3296:U
3294:in
3292:u
3287:do
3279:do
3277:V
3275:in
3273:v
3267:do
3265:U
3263:in
3261:u
3256:is
3232:if
3225:if
3222:do
3218:in
3216:v
3207:if
3204:is
3188:if
3185:do
3181:in
3179:v
3170:if
3166:do
3150:if
3147:do
3145:U
3143:in
3141:u
3136:is
2768:,
2421:.
1751:A
1320:.
1308:.
610:.
4254:.
4249::
4239::
4226:.
4212::
4200:.
4181:.
4167:.
4152::
4133:.
4112::
4096:3
4084:.
4071::
4048:)
4044:|
4040:E
4036:|
4026:|
4022:V
4018:|
4012:(
4009:O
3985:5
3967::
3961:2
3953:n
3940:.
3925::
3882::
3872::
3853:.
3830::
3811:.
3796::
3767:.
3753:.
3719::
3673::
3663::
3647:.
3642::
3616:)
3608:n
3598:m
3586:n
3581:(
3577:O
3560:.
3517:.
3505:.
3457:.
3445:.
3433:.
3101:)
3095:|
3091:V
3087:|
3081:(
3078:O
3040:)
3031:|
3027:V
3023:|
3010:|
3006:E
3002:|
2987:|
2982:V
2978:|
2973:(
2969:O
2945:)
2940:2
2935:|
2930:V
2926:|
2922:(
2916:=
2912:|
2908:E
2904:|
2871:)
2867:|
2863:V
2859:|
2848:|
2844:E
2840:|
2836:(
2833:O
2813:)
2809:|
2805:V
2801:|
2791:(
2788:O
2741:)
2735:|
2731:V
2727:|
2720:|
2716:E
2712:|
2708:(
2705:O
2682:|
2678:V
2674:|
2668:2
2642:|
2638:V
2634:|
2608:|
2604:V
2600:|
2577:M
2554:|
2550:V
2546:|
2520:|
2516:V
2512:|
2499:M
2478:|
2474:V
2470:|
2444:|
2440:V
2436:|
2409:)
2403:|
2399:V
2395:|
2388:|
2384:E
2380:|
2376:(
2373:O
2352:|
2348:E
2344:|
2322:|
2318:V
2314:|
2290:|
2286:V
2282:|
2259:)
2255:|
2251:E
2247:|
2243:(
2240:O
2220:.
2208:M
2185:V
2165:U
2145:)
2141:|
2137:E
2133:|
2129:(
2126:O
2106:U
2086:U
2066:F
2046:U
2026:F
1994:k
1967:F
1947:v
1927:F
1907:k
1887:V
1864:V
1844:k
1824:V
1804:U
1783:U
1763:U
1735:M
1715:V
1695:U
1675:G
1655:V
1635:U
1609:=
1604:P
1576:)
1571:k
1567:P
1552:2
1548:P
1539:1
1535:P
1531:(
1525:M
1519:M
1495:}
1490:k
1486:P
1482:,
1476:,
1471:2
1467:P
1463:,
1458:1
1454:P
1450:{
1442:P
1408:M
1387:E
1381:M
1356:)
1353:E
1350:,
1347:V
1341:U
1338:(
1335:G
1292:V
1272:U
1252:V
1232:U
1201:M
1181:M
1155:M
1134:P
1114:M
1088:M
1067:M
1041:M
1014:M
993:M
973:M
953:P
933:P
907:M
886:M
860:M
833:M
826:M
806:P
786:M
763:1
760:+
756:|
752:M
748:|
727:P
721:M
697:M
677:P
657:M
626:M
587:)
581:|
577:V
573:|
566:|
562:E
558:|
554:(
551:O
531:)
527:|
523:V
519:|
515:(
512:O
492:)
486:|
482:V
478:|
472:(
469:O
410:)
406:|
402:V
398:|
387:|
383:E
379:|
375:(
372:O
348:)
338:|
333:V
329:|
325:(
322:O
298:)
294:|
290:V
286:|
282:(
276:=
272:|
268:E
264:|
243:V
223:E
199:)
193:|
189:V
185:|
178:|
174:E
170:|
166:(
163:O
114:)
111:V
108:(
105:O
74:)
69:V
64:E
61:(
58:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.