1331:
Complexity of
Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20â22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation,
155:
Since each edge in the network has integral capacity, there exists a maximum flow where all flows are integers; these integers must be either 0 or 1 since the all capacities are 1. Each integral flow defines a matching in which an edge is in the matching if and only if its flow is 1. It is a matching
583:
418:
1150:
45:
is adjacent to at most one edge of the subset. As each edge will cover exactly two vertices, this problem is equivalent to the task of finding a matching that covers as many vertices as possible.
1030:
Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; WulffâNilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time",
449:
778:
647:
752:
293:
841:
441:
76:
always connect a left vertex to a right vertex. In this case, the problem can be efficiently solved with simpler algorithms than in the general case.
777:
on bipartite graphs, can be achieved with the much more complicated algorithm of Micali and
Vazirani. The same bound was achieved by an algorithm by
324:
1272:
1198:
Automata, Languages and
Programming, 17th International Colloquium, ICALP90, Warwick University, England, UK, July 16â20, 1990, Proceedings
1154:
1329:
Karp, Richard M. (1972), Miller, Raymond E.; Thatcher, James W.; Bohlinger, Jean D. (eds.), "Reducibility among
Combinatorial Problems",
1222:
1347:
1094:
298:
The algorithm of
Chandran and Hochbaum for bipartite graphs runs in time that depends on the size of the maximum matching
578:{\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).}
937:
1368:
893:
599:
90:
774:
695:
256:
1186:
1032:
998:
Madry, A (2013), "Navigating
Central Path with Electrical Flows: From Flows to Matchings, and Back",
262:
692:
finds a maximum-cardinality matching in general (not necessarily bipartite) graphs. It runs in time
175:
is at most 1, so the incoming flow is at most 1 too, so at most one edge adjacent to each vertex in
164:
is at most 1, so the outgoing flow is at most 1 too, so at most one edge adjacent to each vertex in
810:
907:
885:
859:
851:
34:
1264:
1288:
426:
903:
is a particular maximum-cardinality matching in which prioritized vertices are matched first.
804:
42:
963:
Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm
1063:
1013:
976:
871:
By finding a maximum-cardinality matching, it is possible to decide whether there exists a
800:
94:
27:
8:
850:
Other algorithms for the task are reviewed by Duan and Pettie (see Table I). In terms of
183:
The FordâFulkerson algorithm proceeds by repeatedly finding an augmenting path from some
1017:
980:
1311:
1245:
1167:
1067:
1041:
1003:
966:
889:
985:
the theoretically efficient algorithms listed above tend to perform poorly in practice
259:, which searches for multiple augmenting paths simultaneously. This algorithm runs in
1343:
1315:
1071:
958:
933:
900:
855:
689:
1249:
1171:
1335:
1303:
1237:
1201:
1159:
1051:
872:
1218:
1059:
789:
783:
57:
1339:
1200:, Lecture Notes in Computer Science, vol. 443, Springer, pp. 586â597,
807:
algorithm. This gives a randomized algorithm for general graphs with complexity
1088:
880:
213:
1334:, The IBM Research Symposia Series, Boston, MA: Springer US, pp. 85â103,
1362:
1193:
1084:
793:
653:
892:. If each vertex can be matched to several vertices at once, then this is a
89:
The simplest way to compute a maximum cardinality matching is to follow the
676:
593:
114:
49:
23:
1241:
1000:
Foundations of
Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
1163:
844:
38:
413:{\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}
1205:
1055:
588:
More efficient algorithms exist for special kinds of bipartite graphs:
1307:
1046:
1008:
971:
596:
bipartite graphs, the maximum matching problem can be solved in
255:
An improvement to this algorithm is given by the more elaborate
1223:"Faster scaling algorithms for general graph matching problems"
16:
Graph theory problem: find a matching containing the most edges
1029:
211:(assuming such a path exists). As each path can be found in
1152:
algorithm for finding maximum matching in general graphs",
878:
The problem of finding a matching with maximum weight in a
858:
and the algorithms by Micali and
Vazirani can be seen as
37:
containing as many edges as possible; that is, a maximum
888:, and its restriction to bipartite graphs is called the
1289:"Linear-Time Approximation for Maximum Weight Matching"
1187:"A new approach to maximum matching in general graphs"
1145:{\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}
1098:
675:
is the number of vertices, by reducing the problem to
1332:
1273:
Proc. 45th IEEE Symp. Foundations of
Computer Science
1155:
Proc. 21st IEEE Symp. Foundations of Computer Science
1097:
813:
698:
602:
452:
429:
327:
265:
207:
by taking the symmetric difference of that path with
773:
for general graphs, matching the performance of the
656:
bipartite graphs, the problem can be solved in time
235:, and the maximum matching consists of the edges of
93:. This algorithm solves the more general problem of
52:
of the maximum cardinality matching problem is when
865:
1144:
862:running in linear time for any fixed error bound.
835:
746:
683:
641:
577:
435:
412:
287:
79:
1360:
956:
461:
377:
336:
649:with Madry's algorithm based on electric flows.
1262:
1083:
910:is NP-complete even for 3-uniform hypergraphs.
906:The problem of finding a maximum-cardinality
1265:"Maximum Matchings via Gaussian Elimination"
843:. This is better in theory for sufficiently
399:
380:
364:
339:
1217:
847:, but in practice the algorithm is slower.
1286:
952:
950:
948:
932:(2nd ed.), Prentice Hall, Chapter 3,
423:Using boolean operations on words of size
1045:
1007:
970:
64:are partitioned between left vertices in
945:
84:
1361:
1287:Duan, Ran; Pettie, Seth (2014-01-01).
642:{\displaystyle {\tilde {O}}(E^{10/7})}
443:the complexity is further improved to
250:
171:The outgoing flow from each vertex in
160:The incoming flow into each vertex in
997:
1328:
1256:
1184:
927:
921:
151:Assign a capacity of 1 to each edge.
747:{\displaystyle O(|V|^{2}\cdot |E|)}
41:subset of the edges such that each
13:
140:; add an edge from each vertex in
14:
1380:
1263:Mucha, M.; Sankowski, P. (2004),
1221:; Tarjan, Robert E (1991-10-01).
866:Applications and generalizations
679:with multiple sources and sinks.
1322:
886:maximum weight matching problem
854:, they also point out that the
684:Algorithms for arbitrary graphs
288:{\displaystyle O({\sqrt {V}}E)}
80:Algorithms for bipartite graphs
1280:
1211:
1178:
1138:
1134:
1126:
1116:
1108:
1102:
1077:
1023:
991:
894:generalized assignment problem
830:
817:
741:
737:
729:
715:
706:
702:
636:
615:
609:
513:
505:
500:
492:
478:
470:
351:
343:
282:
269:
1:
914:
799:An alternative approach uses
930:Introduction to Graph Theory
928:West, Douglas Brent (1999),
836:{\displaystyle O(V^{2.372})}
33:, and the goal is to find a
22:is a fundamental problem in
20:Maximum cardinality matching
7:
1340:10.1007/978-1-4684-2001-2_9
10:
1385:
754:. A better performance of
224:time, the running time is
203:and updating the matching
95:computing the maximum flow
1033:SIAM Journal on Computing
803:and is based on the fast
860:approximation algorithms
852:approximation algorithms
436:{\displaystyle \lambda }
91:FordâFulkerson algorithm
1369:Matching (graph theory)
908:matching in hypergraphs
775:HopcroftâKarp algorithm
257:HopcroftâKarp algorithm
1185:Blum, Norbert (1990),
1146:
837:
748:
643:
579:
437:
414:
289:
113:can be converted to a
68:and right vertices in
1242:10.1145/115234.115366
1147:
838:
805:matrix multiplication
749:
644:
580:
438:
415:
290:
239:that carry flow from
1164:10.1109/SFCS.1980.12
1095:
1002:, pp. 253â262,
811:
788:and an algorithm by
696:
600:
450:
427:
325:
263:
121:Add a source vertex
97:. A bipartite graph
85:Flow-based algorithm
1018:2013arXiv1307.2205M
981:2011arXiv1105.1569C
957:Chandran, Bala G.;
251:Advanced algorithms
125:; add an edge from
1296:Journal of the ACM
1276:, pp. 248â255
1230:Journal of the ACM
1206:10.1007/BFb0032060
1158:, pp. 17â27,
1142:
1141:
1056:10.1137/15M1042929
959:Hochbaum, Dorit S.
890:assignment problem
833:
744:
639:
575:
433:
410:
310:| < |
285:
136:Add a sink vertex
129:to each vertex in
1349:978-1-4684-2001-2
1120:
901:priority matching
856:blossom algorithm
690:blossom algorithm
612:
565:
521:
375:
277:
60:, whose vertices
26:. We are given a
1376:
1353:
1352:
1326:
1320:
1319:
1293:
1284:
1278:
1277:
1269:
1260:
1254:
1253:
1227:
1215:
1209:
1208:
1191:
1182:
1176:
1174:
1151:
1149:
1148:
1143:
1137:
1129:
1121:
1119:
1111:
1106:
1081:
1075:
1074:
1049:
1040:(4): 1280â1303,
1027:
1021:
1020:
1011:
995:
989:
987:
974:
954:
943:
942:
925:
873:perfect matching
842:
840:
839:
834:
829:
828:
787:
772:
767:
766:
753:
751:
750:
745:
740:
732:
724:
723:
718:
709:
674:
670:
648:
646:
645:
640:
635:
634:
630:
614:
613:
605:
584:
582:
581:
576:
571:
567:
566:
561:
560:
551:
546:
545:
533:
529:
522:
517:
516:
508:
503:
495:
489:
481:
473:
442:
440:
439:
434:
419:
417:
416:
411:
406:
402:
392:
391:
376:
371:
354:
346:
317:
315:
309:
301:
294:
292:
291:
286:
278:
273:
246:
242:
238:
234:
223:
210:
206:
202:
201:
192:
178:
174:
167:
163:
147:
143:
139:
132:
128:
124:
112:
75:
71:
67:
63:
55:
32:
1384:
1383:
1379:
1378:
1377:
1375:
1374:
1373:
1359:
1358:
1357:
1356:
1350:
1327:
1323:
1308:10.1145/2529989
1291:
1285:
1281:
1267:
1261:
1257:
1225:
1219:Gabow, Harold N
1216:
1212:
1189:
1183:
1179:
1133:
1125:
1115:
1107:
1105:
1096:
1093:
1092:
1089:Vazirani, V. V.
1082:
1078:
1028:
1024:
996:
992:
955:
946:
940:
926:
922:
917:
868:
824:
820:
812:
809:
808:
781:
770:
765:
762:
760:
758:
755:
736:
728:
719:
714:
713:
705:
697:
694:
693:
686:
672:
657:
626:
622:
618:
604:
603:
601:
598:
597:
556:
552:
550:
541:
537:
512:
504:
499:
491:
490:
488:
477:
469:
468:
464:
460:
456:
451:
448:
447:
428:
425:
424:
387:
383:
370:
350:
342:
335:
331:
326:
323:
322:
311:
305:
303:
299:
272:
264:
261:
260:
253:
244:
240:
236:
225:
212:
208:
204:
199:
194:
184:
176:
172:
165:
161:
145:
141:
137:
130:
126:
122:
98:
87:
82:
73:
72:, and edges in
69:
65:
61:
58:bipartite graph
53:
30:
17:
12:
11:
5:
1382:
1372:
1371:
1355:
1354:
1348:
1321:
1279:
1255:
1236:(4): 815â853.
1210:
1194:Paterson, Mike
1177:
1140:
1136:
1132:
1128:
1124:
1118:
1114:
1110:
1104:
1101:
1076:
1022:
990:
944:
938:
919:
918:
916:
913:
912:
911:
904:
897:
884:is called the
881:weighted graph
876:
867:
864:
832:
827:
823:
819:
816:
768:
763:
756:
743:
739:
735:
731:
727:
722:
717:
712:
708:
704:
701:
685:
682:
681:
680:
650:
638:
633:
629:
625:
621:
617:
611:
608:
586:
585:
574:
570:
564:
559:
555:
549:
544:
540:
536:
532:
528:
525:
520:
515:
511:
507:
502:
498:
494:
487:
484:
480:
476:
472:
467:
463:
459:
455:
432:
421:
420:
409:
405:
401:
398:
395:
390:
386:
382:
379:
374:
369:
366:
363:
360:
357:
353:
349:
345:
341:
338:
334:
330:
284:
281:
276:
271:
268:
252:
249:
181:
180:
169:
153:
152:
149:
134:
86:
83:
81:
78:
15:
9:
6:
4:
3:
2:
1381:
1370:
1367:
1366:
1364:
1351:
1345:
1341:
1337:
1333:
1325:
1317:
1313:
1309:
1305:
1301:
1297:
1290:
1283:
1275:
1274:
1266:
1259:
1251:
1247:
1243:
1239:
1235:
1231:
1224:
1220:
1214:
1207:
1203:
1199:
1195:
1188:
1181:
1173:
1169:
1165:
1161:
1157:
1156:
1130:
1122:
1112:
1099:
1090:
1086:
1080:
1073:
1069:
1065:
1061:
1057:
1053:
1048:
1043:
1039:
1035:
1034:
1026:
1019:
1015:
1010:
1005:
1001:
994:
986:
982:
978:
973:
968:
964:
960:
953:
951:
949:
941:
939:0-13-014400-2
935:
931:
924:
920:
909:
905:
902:
898:
895:
891:
887:
883:
882:
877:
874:
870:
869:
863:
861:
857:
853:
848:
846:
825:
821:
814:
806:
802:
801:randomization
797:
795:
791:
785:
780:
776:
733:
725:
720:
710:
699:
691:
678:
668:
664:
660:
655:
651:
631:
627:
623:
619:
606:
595:
591:
590:
589:
572:
568:
562:
557:
553:
547:
542:
538:
534:
530:
526:
523:
518:
509:
496:
485:
482:
474:
465:
457:
453:
446:
445:
444:
430:
407:
403:
396:
393:
388:
384:
372:
367:
361:
358:
355:
347:
332:
328:
321:
320:
319:
314:
308:
296:
279:
274:
266:
258:
248:
232:
228:
221:
217:
216:
197:
191:
187:
170:
159:
158:
157:
150:
135:
120:
119:
118:
116:
110:
106:
102:
96:
92:
77:
59:
51:
48:An important
46:
44:
40:
36:
29:
25:
21:
1330:
1324:
1299:
1295:
1282:
1271:
1258:
1233:
1229:
1213:
1197:
1180:
1153:
1091:(1980), "An
1079:
1037:
1031:
1025:
999:
993:
984:
962:
929:
923:
879:
849:
845:dense graphs
798:
687:
677:maximum flow
666:
662:
658:
587:
422:
312:
306:
302:, which for
297:
254:
230:
226:
219:
214:
195:
189:
185:
182:
154:
117:as follows.
115:flow network
108:
104:
100:
88:
50:special case
47:
24:graph theory
19:
18:
782: [
179:is present.
168:is present.
39:cardinality
1085:Micali, S.
915:References
1316:207208641
1123:⋅
1072:207071917
1047:1105.2228
1009:1307.2205
972:1105.1569
726:⋅
610:~
563:λ
519:λ
431:λ
156:because:
1363:Category
1302:: 1â23.
1250:18350108
1172:27467816
961:(2011),
193:to some
35:matching
1196:(ed.),
1064:3681377
1014:Bibcode
977:Bibcode
761:√
1346:
1314:
1248:
1170:
1070:
1062:
936:
794:Tarjan
671:where
654:planar
594:sparse
316:|
304:|
295:time.
43:vertex
1312:S2CID
1292:(PDF)
1268:(PDF)
1246:S2CID
1226:(PDF)
1192:, in
1190:(PDF)
1168:S2CID
1068:S2CID
1042:arXiv
1004:arXiv
967:arXiv
826:2.372
790:Gabow
786:]
56:is a
28:graph
1344:ISBN
934:ISBN
792:and
779:Blum
688:The
665:log
652:For
592:For
318:is
1336:doi
1304:doi
1238:doi
1202:doi
1160:doi
1052:doi
558:2.5
462:min
378:min
337:min
243:to
144:to
1365::
1342:,
1310:.
1300:61
1298:.
1294:.
1270:,
1244:.
1234:38
1232:.
1228:.
1166:,
1087:;
1066:,
1060:MR
1058:,
1050:,
1038:46
1036:,
1012:,
983:,
975:,
965:,
947:^
899:A
796:.
784:de
624:10
247:.
231:VE
198:â
188:â
107:,
103:+
1338::
1318:.
1306::
1252:.
1240::
1204::
1175:.
1162::
1139:)
1135:|
1131:E
1127:|
1117:|
1113:V
1109:|
1103:(
1100:O
1054::
1044::
1016::
1006::
988:.
979::
969::
896:.
875:.
831:)
822:V
818:(
815:O
771:)
769:E
764:V
759:(
757:O
742:)
738:|
734:E
730:|
721:2
716:|
711:V
707:|
703:(
700:O
673:n
669:)
667:n
663:n
661:(
659:O
637:)
632:7
628:/
620:E
616:(
607:O
573:.
569:)
554:k
548:+
543:2
539:k
535:+
531:}
527:E
524:,
514:|
510:Y
506:|
501:|
497:X
493:|
486:,
483:k
479:|
475:X
471:|
466:{
458:(
454:O
408:.
404:)
400:}
397:E
394:,
389:2
385:k
381:{
373:k
368:+
365:}
362:E
359:,
356:k
352:|
348:X
344:|
340:{
333:(
329:O
313:Y
307:X
300:k
283:)
280:E
275:V
270:(
267:O
245:Y
241:X
237:E
233:)
229:(
227:O
222:)
220:E
218:(
215:O
209:M
205:M
200:Y
196:y
190:X
186:x
177:Y
173:Y
166:X
162:X
148:.
146:t
142:Y
138:t
133:.
131:X
127:s
123:s
111:)
109:E
105:Y
101:X
99:(
74:E
70:Y
66:X
62:V
54:G
31:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.