22:
1507:, the blossom algorithm starts with a small matching and goes through multiple iterations in which it increases the size of the matching by one edge. We can find the Gallai–Edmonds decomposition from the blossom algorithm's work in the last iteration: the work done when it has a maximum matching
699:: each component has an odd number of vertices, and when any one of these vertices is left out, there is a perfect matching of the remaining vertices. In particular, each component has a near-perfect matching: a matching that covers all but one of the vertices.
1129:
2621:
2572:
767:
1851:
2465:
2411:
2345:
2261:
2227:
2311:
2286:
2193:
2168:
2143:
2118:
2093:
2068:
2043:
1998:
1973:
1948:
1876:
1765:
803:
2523:
2494:
2377:
1680:
1475:
1446:
1417:
1322:
1207:
1003:
971:
942:
913:
884:
832:
729:
693:
657:
624:
591:
562:
533:
501:
472:
443:
414:
385:
356:
327:
210:
177:
148:
119:
1368:
1233:
2431:
2018:
1916:
1896:
1805:
1785:
1740:
1720:
1700:
1651:
1631:
1611:
1591:
1548:
1525:
1505:
1388:
1342:
1293:
1273:
1253:
1178:
1158:
1043:
1023:
855:
298:
274:
250:
230:
86:
2638:
An extension of the Gallai–Edmonds decomposition theorem to multi-edge matchings is given in
Katarzyna Paluch's "Capacitated Rank-Maximal Matchings".
2853:
2754:
2632:
627:
1160:
can be found, somewhat inefficiently, by starting with any algorithm for finding a maximum matching. From the definition, a vertex
2879:
1922:
This lemma also implies that when a blossom is contracted, the set of inessential vertices outside the blossom remains the same.
1554:
subgraphs called "blossoms" to single vertices. When this is done in the last iteration, the blossoms have a special property:
38:
1048:
1569:
that starts at a vertex uncovered by the matching. The second property follows from the first by the lemma below:
2874:
2796:
Szabó, Jácint; Loebl, Martin; Janata, Marek (14 February 2005), "The
Edmonds–Gallai Decomposition for the
1484:, and the processing done by this algorithm enables us to find the Gallai–Edmonds decomposition directly.
21:
2738:
696:
2840:, Lecture Notes in Computer Science, vol. 7878, Springer, Berlin, Heidelberg, pp. 324–335,
737:
2819:
2742:
2721:
180:
2577:
2528:
1810:
1565:
The first property follows from the algorithm: every vertex of a blossom is the endpoint of an
2849:
2750:
1566:
1481:
57:
18:
Partition of the vertices of a graph giving information on the structure of maximum matchings
2841:
2809:
2711:
1551:
594:
42:
2436:
2382:
2316:
2232:
2198:
1561:
The vertex formed by contracting the blossom is an inessential vertex of the smaller graph.
772:
2499:
2470:
2353:
1656:
1451:
1422:
1393:
1298:
1183:
979:
947:
918:
889:
860:
808:
705:
669:
633:
600:
567:
538:
509:
477:
448:
419:
390:
361:
332:
303:
186:
153:
124:
95:
25:
An illustration of the three sets in the Gallai–Edmonds decomposition of an example graph.
1347:
1212:
857:
has the following structure: it consists of a near-perfect matching of each component of
2291:
2266:
2173:
2148:
2123:
2098:
2073:
2048:
2023:
1978:
1953:
1928:
1856:
1745:
2416:
2003:
1925:
Once every blossom has been contracted by the algorithm, the result is a smaller graph
1901:
1881:
1790:
1770:
1725:
1705:
1685:
1636:
1616:
1596:
1576:
1533:
1510:
1490:
1373:
1327:
1278:
1258:
1238:
1163:
1143:
1028:
1008:
840:
283:
259:
235:
215:
71:
329:
is defined to contain all the inessential vertices. Essential vertices are split into
2868:
2823:
2725:
2699:
2677:
2655:
89:
50:
46:
30:
2845:
416:
is defined to contain all essential vertices adjacent to at least one vertex of
474:
is defined to contain all essential vertices not adjacent to any vertices of
2120:, the Gallai–Edmonds decomposition has a short description. The vertices in
1480:
One particular method for finding a maximum matching in a graph is
Edmonds'
2716:
2350:
Contracting blossoms preserves the set of inessential vertices; therefore
2836:
Paluch, Katarzyna (22 May 2013), "Capacitated Rank-Maximal
Matchings",
2433:
which were contracted as part of a blossom, as well as all vertices in
1558:
All vertices of a blossom are inessential vertices of the bigger graph.
280:(vertices which are left uncovered by at least one maximum matching in
2145:
are classified into inner vertices (vertices at an odd distance in
56:
The Gallai–Edmonds decomposition of a graph can be found using the
2814:
41:
into three subsets which provides information on the structure of
2170:
from a root) and outer vertices (vertices at an even distance in
1025:
components, then the number of edges in any maximum matching in
662:
The Gallai–Edmonds decomposition has the following properties:
53:
independently discovered it and proved its key properties.
256:(vertices which are covered by every maximum matching in
2631:
The Gallai–Edmonds decomposition is a generalization of
1530:
In every iteration, the blossom algorithm passes from
597:
by those sets. For example, we say "the components of
2580:
2531:
2502:
2473:
2439:
2419:
2385:
2356:
2319:
2294:
2269:
2235:
2201:
2176:
2151:
2126:
2101:
2076:
2051:
2026:
2006:
1981:
1956:
1931:
1904:
1884:
1859:
1813:
1793:
1773:
1748:
1728:
1708:
1688:
1659:
1639:
1619:
1599:
1579:
1536:
1513:
1493:
1454:
1425:
1396:
1376:
1350:
1330:
1301:
1281:
1261:
1241:
1215:
1186:
1166:
1146:
1051:
1031:
1011:
982:
950:
921:
892:
863:
843:
811:
775:
740:
708:
672:
636:
603:
570:
541:
512:
480:
451:
422:
393:
364:
335:
306:
286:
262:
238:
218:
189:
156:
127:
98:
88:, its Gallai–Edmonds decomposition consists of three
74:
2615:
2566:
2517:
2488:
2459:
2425:
2405:
2371:
2339:
2305:
2280:
2263:is exactly the set of outer vertices. Vertices of
2255:
2221:
2187:
2162:
2137:
2112:
2087:
2062:
2037:
2012:
1992:
1967:
1942:
1910:
1890:
1870:
1845:
1799:
1779:
1759:
1734:
1714:
1694:
1674:
1645:
1625:
1605:
1585:
1542:
1519:
1499:
1469:
1440:
1411:
1382:
1362:
1336:
1316:
1287:
1267:
1247:
1227:
1201:
1172:
1152:
1123:
1037:
1017:
997:
965:
936:
907:
878:
849:
826:
797:
761:
723:
687:
651:
618:
585:
556:
527:
495:
466:
437:
408:
379:
350:
321:
292:
268:
244:
224:
204:
171:
142:
113:
80:
2680:(1964), "Maximale Systeme unabhängiger Kanten",
1124:{\displaystyle {\frac {1}{2}}(|V(G)|-k+|A(G)|)}
1275:) has a maximum matching of the same size as
8:
2786:Exercise 9.1.2 in Lovász and Plummer, p. 360
2749:(1st ed.), North-Holland, Section 3.2,
1140:The Gallai–Edmonds decomposition of a graph
2768:Theorem 3.2.1 in Lovász and Plummer, p. 94
2229:is exactly the set of inner vertices, and
2813:
2777:Lemma 9.1.1 in Lovász and Plummer, p. 358
2715:
2635:from bipartite graphs to general graphs.
2579:
2530:
2501:
2472:
2438:
2418:
2384:
2355:
2318:
2293:
2268:
2234:
2200:
2175:
2150:
2125:
2100:
2075:
2050:
2025:
2005:
1980:
1955:
1930:
1903:
1883:
1858:
1812:
1792:
1772:
1747:
1727:
1707:
1687:
1658:
1638:
1618:
1598:
1578:
1535:
1512:
1492:
1453:
1424:
1395:
1375:
1349:
1329:
1300:
1280:
1260:
1240:
1214:
1185:
1165:
1145:
1113:
1096:
1082:
1065:
1052:
1050:
1030:
1010:
981:
949:
920:
891:
862:
842:
810:
784:
776:
774:
739:
707:
671:
635:
602:
569:
540:
511:
479:
450:
421:
392:
363:
334:
305:
285:
261:
237:
217:
188:
155:
126:
97:
73:
2682:Magyar Tud. Akad. Mat. Kutato Int. Kozl.
2660:Magyar Tud. Akad. Mat. Kutato Int. Kozl.
1722:and is vertex-disjoint from the rest of
20:
2802:The Electronic Journal of Combinatorics
2647:
1527:, which it fails to make any larger.
1487:To find a maximum matching in a graph
2702:(1965), "Paths, trees, and flowers",
7:
37:is a partition of the vertices of a
1324:by computing a maximum matching in
506:It is common to identify the sets
14:
915:, and edges from all vertices in
2658:(1963), "Kritische graphen II",
2633:Dulmage–Mendelsohn decomposition
2704:Canadian Journal of Mathematics
762:{\displaystyle X\subseteq A(G)}
2610:
2599:
2590:
2584:
2561:
2550:
2541:
2535:
2512:
2506:
2483:
2477:
2454:
2443:
2400:
2389:
2366:
2360:
2334:
2323:
2250:
2239:
2216:
2205:
1840:
1834:
1477:directly from the definition.
1464:
1458:
1435:
1429:
1406:
1400:
1311:
1305:
1196:
1190:
1118:
1114:
1110:
1104:
1097:
1083:
1079:
1073:
1066:
1062:
992:
986:
960:
954:
931:
925:
902:
896:
873:
867:
821:
815:
785:
777:
756:
750:
718:
712:
682:
676:
646:
640:
613:
607:
580:
574:
551:
545:
522:
516:
490:
484:
461:
455:
432:
426:
403:
397:
374:
368:
345:
339:
316:
310:
199:
193:
166:
160:
137:
131:
108:
102:
1:
212:: the set of all vertices of
2846:10.1007/978-3-642-38233-8_27
2020:, and an alternating forest
1295:. Therefore we can identify
35:Gallai–Edmonds decomposition
630:of the subgraph induced by
2896:
2616:{\displaystyle C(G)=C(G')}
2567:{\displaystyle A(G)=A(G')}
2413:by taking all vertices of
944:to distinct components of
837:Every maximum matching in
769:has neighbors in at least
2838:Algorithms and Complexity
2800:-Piece Packing Problem",
1898:is a maximum matching in
1853:is a maximum matching in
1846:{\displaystyle M'=M-E(Z)}
1807:to a single vertex. Then
1235:(the graph obtained from
232:. First, the vertices of
1742:. Construct a new graph
1419:can be partitioned into
886:, a perfect matching of
702:The subgraph induced by
2880:Matching (graph theory)
734:Every non-empty subset
731:has a perfect matching.
2717:10.4153/CJM-1965-045-4
2617:
2568:
2525:are never contracted;
2519:
2490:
2461:
2427:
2407:
2373:
2341:
2307:
2282:
2257:
2223:
2189:
2164:
2139:
2114:
2089:
2064:
2039:
2014:
1994:
1969:
1944:
1912:
1892:
1872:
1847:
1801:
1781:
1761:
1736:
1716:
1696:
1676:
1647:
1627:
1607:
1587:
1544:
1521:
1501:
1471:
1442:
1413:
1384:
1364:
1338:
1318:
1289:
1269:
1249:
1229:
1203:
1174:
1154:
1125:
1039:
1019:
999:
967:
938:
909:
880:
851:
828:
799:
763:
725:
697:factor-critical graphs
689:
653:
620:
587:
558:
529:
497:
468:
439:
410:
381:
352:
323:
294:
270:
246:
226:
206:
173:
144:
115:
82:
26:
2618:
2569:
2520:
2491:
2462:
2460:{\displaystyle D(G')}
2428:
2408:
2406:{\displaystyle D(G')}
2374:
2342:
2340:{\displaystyle C(G')}
2308:
2283:
2258:
2256:{\displaystyle D(G')}
2224:
2222:{\displaystyle A(G')}
2190:
2165:
2140:
2115:
2090:
2065:
2040:
2015:
1995:
1970:
1950:, a maximum matching
1945:
1913:
1893:
1873:
1848:
1802:
1782:
1762:
1737:
1717:
1697:
1677:
1653:be a cycle of length
1648:
1628:
1608:
1588:
1550:to smaller graphs by
1545:
1522:
1502:
1472:
1443:
1414:
1385:
1365:
1339:
1319:
1290:
1270:
1250:
1230:
1204:
1175:
1155:
1126:
1040:
1020:
1000:
968:
939:
910:
881:
852:
829:
800:
798:{\displaystyle |X|+1}
764:
726:
690:
654:
621:
588:
559:
530:
498:
469:
440:
411:
382:
353:
324:
295:
271:
247:
227:
207:
174:
145:
116:
83:
24:
2578:
2529:
2518:{\displaystyle C(G)}
2500:
2489:{\displaystyle A(G)}
2471:
2437:
2417:
2383:
2372:{\displaystyle D(G)}
2354:
2317:
2292:
2267:
2233:
2199:
2174:
2149:
2124:
2099:
2074:
2049:
2024:
2004:
2000:of the same size as
1979:
1954:
1929:
1902:
1882:
1857:
1811:
1791:
1771:
1746:
1726:
1706:
1686:
1675:{\displaystyle 2k+1}
1657:
1637:
1617:
1597:
1577:
1534:
1511:
1491:
1470:{\displaystyle C(G)}
1452:
1441:{\displaystyle A(G)}
1423:
1412:{\displaystyle D(G)}
1394:
1390:. The complement of
1374:
1348:
1328:
1317:{\displaystyle D(G)}
1299:
1279:
1259:
1239:
1213:
1202:{\displaystyle D(G)}
1184:
1164:
1144:
1049:
1029:
1009:
998:{\displaystyle D(G)}
980:
966:{\displaystyle D(G)}
948:
937:{\displaystyle A(G)}
919:
908:{\displaystyle C(G)}
890:
879:{\displaystyle D(G)}
861:
841:
827:{\displaystyle D(G)}
809:
773:
738:
724:{\displaystyle C(G)}
706:
688:{\displaystyle D(G)}
670:
652:{\displaystyle D(G)}
634:
628:connected components
619:{\displaystyle D(G)}
601:
586:{\displaystyle D(G)}
568:
557:{\displaystyle C(G)}
539:
528:{\displaystyle A(G)}
510:
496:{\displaystyle D(G)}
478:
467:{\displaystyle C(G)}
449:
438:{\displaystyle D(G)}
420:
409:{\displaystyle A(G)}
391:
380:{\displaystyle C(G)}
362:
351:{\displaystyle A(G)}
333:
322:{\displaystyle D(G)}
304:
284:
278:inessential vertices
260:
236:
216:
205:{\displaystyle V(G)}
187:
172:{\displaystyle D(G)}
154:
143:{\displaystyle C(G)}
125:
114:{\displaystyle A(G)}
96:
72:
2743:Plummer, Michael D.
1363:{\displaystyle G-v}
1228:{\displaystyle G-v}
593:with the subgraphs
2613:
2564:
2515:
2486:
2467:. The vertices in
2457:
2423:
2403:
2379:can be found from
2369:
2337:
2306:{\displaystyle F'}
2303:
2281:{\displaystyle G'}
2278:
2253:
2219:
2188:{\displaystyle F'}
2185:
2163:{\displaystyle F'}
2160:
2138:{\displaystyle F'}
2135:
2113:{\displaystyle G'}
2110:
2088:{\displaystyle M'}
2085:
2063:{\displaystyle G'}
2060:
2038:{\displaystyle F'}
2035:
2010:
1993:{\displaystyle G'}
1990:
1968:{\displaystyle M'}
1965:
1943:{\displaystyle G'}
1940:
1908:
1888:
1871:{\displaystyle G'}
1868:
1843:
1797:
1777:
1760:{\displaystyle G'}
1757:
1732:
1712:
1692:
1672:
1643:
1623:
1603:
1583:
1540:
1517:
1497:
1467:
1438:
1409:
1380:
1360:
1334:
1314:
1285:
1265:
1245:
1225:
1199:
1170:
1150:
1121:
1035:
1015:
995:
963:
934:
905:
876:
847:
824:
795:
759:
721:
685:
666:The components of
649:
616:
583:
554:
525:
493:
464:
435:
406:
377:
348:
319:
290:
266:
254:essential vertices
242:
222:
202:
169:
140:
111:
78:
27:
2855:978-3-642-38232-1
2756:978-0-8218-4759-6
2426:{\displaystyle G}
2013:{\displaystyle M}
1911:{\displaystyle G}
1891:{\displaystyle M}
1800:{\displaystyle Z}
1780:{\displaystyle G}
1735:{\displaystyle M}
1715:{\displaystyle M}
1695:{\displaystyle k}
1646:{\displaystyle Z}
1626:{\displaystyle G}
1606:{\displaystyle M}
1586:{\displaystyle G}
1543:{\displaystyle G}
1520:{\displaystyle M}
1500:{\displaystyle G}
1482:blossom algorithm
1383:{\displaystyle v}
1370:for every vertex
1337:{\displaystyle G}
1288:{\displaystyle G}
1268:{\displaystyle v}
1248:{\displaystyle G}
1173:{\displaystyle v}
1153:{\displaystyle G}
1060:
1038:{\displaystyle G}
1018:{\displaystyle k}
850:{\displaystyle G}
293:{\displaystyle G}
269:{\displaystyle G}
252:are divided into
245:{\displaystyle G}
225:{\displaystyle G}
81:{\displaystyle G}
58:blossom algorithm
43:maximum matchings
2887:
2875:Graph algorithms
2859:
2858:
2833:
2827:
2826:
2817:
2793:
2787:
2784:
2778:
2775:
2769:
2766:
2760:
2759:
2735:
2729:
2728:
2719:
2696:
2690:
2689:
2674:
2668:
2667:
2652:
2622:
2620:
2619:
2614:
2609:
2573:
2571:
2570:
2565:
2560:
2524:
2522:
2521:
2516:
2495:
2493:
2492:
2487:
2466:
2464:
2463:
2458:
2453:
2432:
2430:
2429:
2424:
2412:
2410:
2409:
2404:
2399:
2378:
2376:
2375:
2370:
2346:
2344:
2343:
2338:
2333:
2312:
2310:
2309:
2304:
2302:
2288:that are not in
2287:
2285:
2284:
2279:
2277:
2262:
2260:
2259:
2254:
2249:
2228:
2226:
2225:
2220:
2215:
2194:
2192:
2191:
2186:
2184:
2169:
2167:
2166:
2161:
2159:
2144:
2142:
2141:
2136:
2134:
2119:
2117:
2116:
2111:
2109:
2094:
2092:
2091:
2086:
2084:
2070:with respect to
2069:
2067:
2066:
2061:
2059:
2044:
2042:
2041:
2036:
2034:
2019:
2017:
2016:
2011:
1999:
1997:
1996:
1991:
1989:
1974:
1972:
1971:
1966:
1964:
1949:
1947:
1946:
1941:
1939:
1917:
1915:
1914:
1909:
1897:
1895:
1894:
1889:
1877:
1875:
1874:
1869:
1867:
1852:
1850:
1849:
1844:
1821:
1806:
1804:
1803:
1798:
1786:
1784:
1783:
1778:
1766:
1764:
1763:
1758:
1756:
1741:
1739:
1738:
1733:
1721:
1719:
1718:
1713:
1701:
1699:
1698:
1693:
1681:
1679:
1678:
1673:
1652:
1650:
1649:
1644:
1632:
1630:
1629:
1624:
1612:
1610:
1609:
1604:
1592:
1590:
1589:
1584:
1567:alternating path
1549:
1547:
1546:
1541:
1526:
1524:
1523:
1518:
1506:
1504:
1503:
1498:
1476:
1474:
1473:
1468:
1447:
1445:
1444:
1439:
1418:
1416:
1415:
1410:
1389:
1387:
1386:
1381:
1369:
1367:
1366:
1361:
1343:
1341:
1340:
1335:
1323:
1321:
1320:
1315:
1294:
1292:
1291:
1286:
1274:
1272:
1271:
1266:
1254:
1252:
1251:
1246:
1234:
1232:
1231:
1226:
1208:
1206:
1205:
1200:
1179:
1177:
1176:
1171:
1159:
1157:
1156:
1151:
1130:
1128:
1127:
1122:
1117:
1100:
1086:
1069:
1061:
1053:
1044:
1042:
1041:
1036:
1024:
1022:
1021:
1016:
1004:
1002:
1001:
996:
972:
970:
969:
964:
943:
941:
940:
935:
914:
912:
911:
906:
885:
883:
882:
877:
856:
854:
853:
848:
833:
831:
830:
825:
804:
802:
801:
796:
788:
780:
768:
766:
765:
760:
730:
728:
727:
722:
694:
692:
691:
686:
658:
656:
655:
650:
625:
623:
622:
617:
592:
590:
589:
584:
563:
561:
560:
555:
534:
532:
531:
526:
502:
500:
499:
494:
473:
471:
470:
465:
444:
442:
441:
436:
415:
413:
412:
407:
386:
384:
383:
378:
357:
355:
354:
349:
328:
326:
325:
320:
299:
297:
296:
291:
275:
273:
272:
267:
251:
249:
248:
243:
231:
229:
228:
223:
211:
209:
208:
203:
178:
176:
175:
170:
149:
147:
146:
141:
120:
118:
117:
112:
87:
85:
84:
79:
2895:
2894:
2890:
2889:
2888:
2886:
2885:
2884:
2865:
2864:
2863:
2862:
2856:
2835:
2834:
2830:
2795:
2794:
2790:
2785:
2781:
2776:
2772:
2767:
2763:
2757:
2747:Matching Theory
2737:
2736:
2732:
2698:
2697:
2693:
2676:
2675:
2671:
2654:
2653:
2649:
2644:
2629:
2627:Generalizations
2602:
2576:
2575:
2553:
2527:
2526:
2498:
2497:
2469:
2468:
2446:
2435:
2434:
2415:
2414:
2392:
2381:
2380:
2352:
2351:
2326:
2315:
2314:
2295:
2290:
2289:
2270:
2265:
2264:
2242:
2231:
2230:
2208:
2197:
2196:
2177:
2172:
2171:
2152:
2147:
2146:
2127:
2122:
2121:
2102:
2097:
2096:
2077:
2072:
2071:
2052:
2047:
2046:
2027:
2022:
2021:
2002:
2001:
1982:
1977:
1976:
1957:
1952:
1951:
1932:
1927:
1926:
1900:
1899:
1880:
1879:
1878:if and only if
1860:
1855:
1854:
1814:
1809:
1808:
1789:
1788:
1769:
1768:
1749:
1744:
1743:
1724:
1723:
1704:
1703:
1684:
1683:
1682:which contains
1655:
1654:
1635:
1634:
1615:
1614:
1595:
1594:
1575:
1574:
1532:
1531:
1509:
1508:
1489:
1488:
1450:
1449:
1421:
1420:
1392:
1391:
1372:
1371:
1346:
1345:
1326:
1325:
1297:
1296:
1277:
1276:
1257:
1256:
1237:
1236:
1211:
1210:
1209:if and only if
1182:
1181:
1162:
1161:
1142:
1141:
1138:
1047:
1046:
1027:
1026:
1007:
1006:
978:
977:
946:
945:
917:
916:
888:
887:
859:
858:
839:
838:
807:
806:
771:
770:
736:
735:
704:
703:
668:
667:
632:
631:
599:
598:
566:
565:
537:
536:
508:
507:
476:
475:
447:
446:
418:
417:
389:
388:
360:
359:
331:
330:
302:
301:
282:
281:
258:
257:
234:
233:
214:
213:
185:
184:
152:
151:
123:
122:
94:
93:
70:
69:
66:
19:
12:
11:
5:
2893:
2891:
2883:
2882:
2877:
2867:
2866:
2861:
2860:
2854:
2828:
2788:
2779:
2770:
2761:
2755:
2739:Lovász, László
2730:
2691:
2669:
2646:
2645:
2643:
2640:
2628:
2625:
2612:
2608:
2605:
2601:
2598:
2595:
2592:
2589:
2586:
2583:
2563:
2559:
2556:
2552:
2549:
2546:
2543:
2540:
2537:
2534:
2514:
2511:
2508:
2505:
2485:
2482:
2479:
2476:
2456:
2452:
2449:
2445:
2442:
2422:
2402:
2398:
2395:
2391:
2388:
2368:
2365:
2362:
2359:
2336:
2332:
2329:
2325:
2322:
2301:
2298:
2276:
2273:
2252:
2248:
2245:
2241:
2238:
2218:
2214:
2211:
2207:
2204:
2195:from a root);
2183:
2180:
2158:
2155:
2133:
2130:
2108:
2105:
2083:
2080:
2058:
2055:
2033:
2030:
2009:
1988:
1985:
1963:
1960:
1938:
1935:
1920:
1919:
1907:
1887:
1866:
1863:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1820:
1817:
1796:
1776:
1755:
1752:
1731:
1711:
1691:
1671:
1668:
1665:
1662:
1642:
1622:
1613:a matching in
1602:
1582:
1563:
1562:
1559:
1539:
1516:
1496:
1466:
1463:
1460:
1457:
1437:
1434:
1431:
1428:
1408:
1405:
1402:
1399:
1379:
1359:
1356:
1353:
1333:
1313:
1310:
1307:
1304:
1284:
1264:
1244:
1224:
1221:
1218:
1198:
1195:
1192:
1189:
1169:
1149:
1137:
1134:
1133:
1132:
1120:
1116:
1112:
1109:
1106:
1103:
1099:
1095:
1092:
1089:
1085:
1081:
1078:
1075:
1072:
1068:
1064:
1059:
1056:
1034:
1014:
994:
991:
988:
985:
974:
962:
959:
956:
953:
933:
930:
927:
924:
904:
901:
898:
895:
875:
872:
869:
866:
846:
835:
823:
820:
817:
814:
805:components of
794:
791:
787:
783:
779:
758:
755:
752:
749:
746:
743:
732:
720:
717:
714:
711:
700:
684:
681:
678:
675:
648:
645:
642:
639:
626:" to mean the
615:
612:
609:
606:
582:
579:
576:
573:
553:
550:
547:
544:
524:
521:
518:
515:
492:
489:
486:
483:
463:
460:
457:
454:
434:
431:
428:
425:
405:
402:
399:
396:
376:
373:
370:
367:
347:
344:
341:
338:
318:
315:
312:
309:
289:
265:
241:
221:
201:
198:
195:
192:
168:
165:
162:
159:
139:
136:
133:
130:
110:
107:
104:
101:
77:
68:Given a graph
65:
62:
45:in the graph.
17:
13:
10:
9:
6:
4:
3:
2:
2892:
2881:
2878:
2876:
2873:
2872:
2870:
2857:
2851:
2847:
2843:
2839:
2832:
2829:
2825:
2821:
2816:
2815:10.37236/1905
2811:
2807:
2803:
2799:
2792:
2789:
2783:
2780:
2774:
2771:
2765:
2762:
2758:
2752:
2748:
2744:
2740:
2734:
2731:
2727:
2723:
2718:
2713:
2709:
2705:
2701:
2700:Edmonds, Jack
2695:
2692:
2687:
2683:
2679:
2678:Gallai, Tibor
2673:
2670:
2665:
2661:
2657:
2656:Gallai, Tibor
2651:
2648:
2641:
2639:
2636:
2634:
2626:
2624:
2606:
2603:
2596:
2593:
2587:
2581:
2557:
2554:
2547:
2544:
2538:
2532:
2509:
2503:
2480:
2474:
2450:
2447:
2440:
2420:
2396:
2393:
2386:
2363:
2357:
2348:
2330:
2327:
2320:
2299:
2296:
2274:
2271:
2246:
2243:
2236:
2212:
2209:
2202:
2181:
2178:
2156:
2153:
2131:
2128:
2106:
2103:
2081:
2078:
2056:
2053:
2031:
2028:
2007:
1986:
1983:
1961:
1958:
1936:
1933:
1923:
1905:
1885:
1864:
1861:
1837:
1831:
1828:
1825:
1822:
1818:
1815:
1794:
1787:by shrinking
1774:
1753:
1750:
1729:
1709:
1689:
1669:
1666:
1663:
1660:
1640:
1620:
1600:
1580:
1572:
1571:
1570:
1568:
1560:
1557:
1556:
1555:
1553:
1537:
1528:
1514:
1494:
1485:
1483:
1478:
1461:
1455:
1432:
1426:
1403:
1397:
1377:
1357:
1354:
1351:
1331:
1308:
1302:
1282:
1262:
1242:
1222:
1219:
1216:
1193:
1187:
1167:
1147:
1135:
1107:
1101:
1093:
1090:
1087:
1076:
1070:
1057:
1054:
1032:
1012:
989:
983:
975:
957:
951:
928:
922:
899:
893:
870:
864:
844:
836:
818:
812:
792:
789:
781:
753:
747:
744:
741:
733:
715:
709:
701:
698:
679:
673:
665:
664:
663:
660:
643:
637:
629:
610:
604:
596:
577:
571:
548:
542:
519:
513:
504:
487:
481:
458:
452:
429:
423:
400:
394:
371:
365:
342:
336:
313:
307:
287:
279:
263:
255:
239:
219:
196:
190:
182:
163:
157:
134:
128:
105:
99:
92:of vertices,
91:
90:disjoint sets
75:
63:
61:
59:
54:
52:
48:
44:
40:
36:
32:
23:
16:
2837:
2831:
2805:
2801:
2797:
2791:
2782:
2773:
2764:
2746:
2733:
2707:
2703:
2694:
2685:
2681:
2672:
2663:
2659:
2650:
2637:
2630:
2349:
1924:
1921:
1593:be a graph,
1564:
1529:
1486:
1479:
1255:by deleting
1139:
1136:Construction
661:
505:
277:
253:
67:
55:
51:Jack Edmonds
47:Tibor Gallai
34:
31:graph theory
28:
15:
2710:: 449–467,
1552:contracting
300:). The set
2869:Categories
2642:References
1633:, and let
387:: the set
64:Properties
2688:: 401–413
2666:: 373–395
1829:−
1702:edges of
1355:−
1220:−
1088:−
745:⊆
2824:11992200
2745:(1986),
2726:18909734
2607:′
2558:′
2451:′
2397:′
2331:′
2300:′
2275:′
2247:′
2213:′
2182:′
2157:′
2132:′
2107:′
2082:′
2057:′
2032:′
1987:′
1962:′
1937:′
1865:′
1819:′
1754:′
179:, whose
1344:and in
595:induced
2852:
2822:
2753:
2724:
1180:is in
564:, and
445:, and
276:) and
150:, and
33:, the
2820:S2CID
2722:S2CID
2313:form
2095:. In
1767:from
181:union
39:graph
2850:ISBN
2751:ISBN
2574:and
2496:and
1573:Let
1448:and
1005:has
695:are
358:and
49:and
2842:doi
2810:doi
2712:doi
2045:in
1975:in
1045:is
976:If
183:is
29:In
2871::
2848:,
2818:,
2808:,
2806:12
2804:,
2741:;
2720:,
2708:17
2706:,
2684:,
2662:,
2623:.
2347:.
659:.
535:,
503:.
121:,
60:.
2844::
2812::
2798:k
2714::
2686:9
2664:8
2611:)
2604:G
2600:(
2597:C
2594:=
2591:)
2588:G
2585:(
2582:C
2562:)
2555:G
2551:(
2548:A
2545:=
2542:)
2539:G
2536:(
2533:A
2513:)
2510:G
2507:(
2504:C
2484:)
2481:G
2478:(
2475:A
2455:)
2448:G
2444:(
2441:D
2421:G
2401:)
2394:G
2390:(
2387:D
2367:)
2364:G
2361:(
2358:D
2335:)
2328:G
2324:(
2321:C
2297:F
2272:G
2251:)
2244:G
2240:(
2237:D
2217:)
2210:G
2206:(
2203:A
2179:F
2154:F
2129:F
2104:G
2079:M
2054:G
2029:F
2008:M
1984:G
1959:M
1934:G
1918:.
1906:G
1886:M
1862:G
1841:)
1838:Z
1835:(
1832:E
1826:M
1823:=
1816:M
1795:Z
1775:G
1751:G
1730:M
1710:M
1690:k
1670:1
1667:+
1664:k
1661:2
1641:Z
1621:G
1601:M
1581:G
1538:G
1515:M
1495:G
1465:)
1462:G
1459:(
1456:C
1436:)
1433:G
1430:(
1427:A
1407:)
1404:G
1401:(
1398:D
1378:v
1358:v
1352:G
1332:G
1312:)
1309:G
1306:(
1303:D
1283:G
1263:v
1243:G
1223:v
1217:G
1197:)
1194:G
1191:(
1188:D
1168:v
1148:G
1131:.
1119:)
1115:|
1111:)
1108:G
1105:(
1102:A
1098:|
1094:+
1091:k
1084:|
1080:)
1077:G
1074:(
1071:V
1067:|
1063:(
1058:2
1055:1
1033:G
1013:k
993:)
990:G
987:(
984:D
973:.
961:)
958:G
955:(
952:D
932:)
929:G
926:(
923:A
903:)
900:G
897:(
894:C
874:)
871:G
868:(
865:D
845:G
834:.
822:)
819:G
816:(
813:D
793:1
790:+
786:|
782:X
778:|
757:)
754:G
751:(
748:A
742:X
719:)
716:G
713:(
710:C
683:)
680:G
677:(
674:D
647:)
644:G
641:(
638:D
614:)
611:G
608:(
605:D
581:)
578:G
575:(
572:D
552:)
549:G
546:(
543:C
523:)
520:G
517:(
514:A
491:)
488:G
485:(
482:D
462:)
459:G
456:(
453:C
433:)
430:G
427:(
424:D
404:)
401:G
398:(
395:A
375:)
372:G
369:(
366:C
346:)
343:G
340:(
337:A
317:)
314:G
311:(
308:D
288:G
264:G
240:G
220:G
200:)
197:G
194:(
191:V
167:)
164:G
161:(
158:D
138:)
135:G
132:(
129:C
109:)
106:G
103:(
100:A
76:G
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
