343:
290:
853:
2588:. Edge dominating set (decision version) is discussed under the dominating set problem, which is the problem GT2 in Appendix A1.1. Minimum maximal matching (decision version) is the problem GT10 in Appendix A1.1.
1866:
edges in polynomial time. Therefore, the problem of finding a minimum maximal matching is essentially equal to the problem of finding a minimum edge dominating set. Both of these two optimization problems are known to be
974:
2572:
1185:
2144:
In the online setting, nodes on one side of the bipartite graph arrive one at a time and must either be immediately matched to the other side of the graph or discarded. This is a natural generalization of the
480:
of vertices, and near-perfect matchings are maximum matchings. In the above figure, part (c) shows a near-perfect matching. If every vertex is unmatched by some near-perfect matching, then the graph is called
336:
is the size of a maximum matching. Every maximum matching is maximal, but not every maximal matching is a maximum matching. The following figure shows examples of maximum matchings in the same three graphs.
2604:. Minimum edge dominating set (optimisation version) is the problem GT3 in Appendix B (page 370). Minimum maximal matching (optimisation version) is the problem GT10 in Appendix B (page 374). See also
1531:
858:
In particular, this shows that any maximal matching is a 2-approximation of a maximum matching and also a 2-approximation of a minimum maximal matching. This inequality is tight: for example, if
2368:
701:
1441:
179:
2863:
2076:
465:
1753:
2308:, a partition of the vertices of a bipartite graph into subsets such that each edge belongs to a perfect matching if and only if its endpoints belong to the same subset
1917:
of an arbitrary 0–1 matrix (another #P-complete problem) is the same as computing the number of perfect matchings in the bipartite graph having the given matrix as its
1813:
1697:
411:
3112:
1027:
330:
2114:
3247:
2031:
2475:
Keivan
Hassani Monfared and Sudipta Mallik, Theorem 3.6, Spectral characterization of matchings in graphs, Linear Algebra and its Applications 496 (2016) 407–419,
1214:
1989:
One of the basic problems in matching theory is to find in a given graph all edges that may be extended to a maximum matching in the graph (such edges are called
1257:
1341:
1321:
1301:
1281:
1234:
1114:
1094:
1071:
1051:
994:
909:
885:
172:
300:(also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. There may be many maximum matchings. The
1921:. However, there exists a fully polynomial time randomized approximation scheme for counting the number of bipartite matchings. A remarkable theorem of
712:
2229:
2149:
and has applications to online ad auctions. The best online algorithm, for the unweighted maximization case with a random arrival model, attains a
2150:
914:
165:
1638:
the optimization problem is to find a maximum-weight matching; a dual problem is to find a minimum-weight matching. This problem is often called
1122:
3202:
2305:
2974:
Mahdian, Mohammad; Yan, Qiqi (2011). "Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs".
61:. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a
2165:
1960: − 1)!!. The numbers of matchings in complete graphs, without constraining the matchings to be perfect, are given by the
3237:
2274:
2418:
Cameron, Kathie (1989), "Induced matchings", Special issue for First
Montreal Conference on Combinatorics and Computer Science, 1987,
3242:
3097:
3054:
2958:
2582:
476:
is one in which exactly one vertex is unmatched. Clearly, a graph can only contain a near-perfect matching when the graph has an
3232:
2735:
2492:
Fredman, Michael L.; Tarjan, Robert Endre (1987), "Fibonacci heaps and their uses in improved network optimization algorithms",
1816:
1540:
is the number of vertices in the graph. Each type has its uses; for more information see the article on matching polynomials.
2598:
Ausiello, Giorgio; Crescenzi, Pierluigi; Gambosi, Giorgio; Kann, Viggo; Marchetti-Spaccamela, Alberto; Protasi, Marco (2003),
496:
is a path that begins with an unmatched vertex and whose edges belong alternately to the matching and not to the matching. An
1961:
127:
1652:
solves the assignment problem and it was one of the beginnings of combinatorial optimization algorithms. It uses a modified
864:
is a path with 3 edges and 4 vertices, the size of a minimum maximal matching is 1 and the size of a maximum matching is 2.
1452:
537:
equals the number of vertices. If there is a perfect matching, then both the matching number and the edge cover number are
642:
2895:
2420:
2280:
1577:
1556:
888:
198:
50:
867:
A spectral characterization of the matching number of a graph is given by
Hassani Monfared and Mallik as follows: Let
1657:
355:
is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is
3087:
2187:
1562:
2867:
2648:
2646:; Vigoda, Eric (2008). "Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems".
2268:
1390:
417:
is used. In the above figure, only part (b) shows a perfect matching. A perfect matching is also a minimum-size
1990:
1984:
2811:
2177:
2036:
2347:
2293:
2255:
2244:
2173:
1914:
1876:
1772:
1624:
1608:
1581:
2770:
Rabin, Michael O.; Vazirani, Vijay V. (1989), "Maximum matchings in general graphs through randomization",
2781:
2657:
2341:
2248:
426:
3038:
1702:
2772:
1074:
482:
58:
3218:
A graph library with
Hopcroft–Karp and Push–Relabel-based maximum cardinality matching implementation
2600:
Complexity and
Approximation: Combinatorial Optimization Problems and Their Approximability Properties
3075:
2708:
2329:
1604:
534:
356:
134:
2786:
2081:
For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time
3000:
2317:
2299:
1851:
1649:
1358:
1352:
231:
139:
54:
2662:
1835:
maximal matching in polynomial time. However, no polynomial-time algorithm is known for finding a
3165:
3146:
3137:
3042:
2698:
2675:
2513:
2494:
2225:
1918:
1756:
1644:
75:
2383:
Each node is incident to at most one edge in the matching. The edges are said to be independent.
1779:
1663:
362:
3198:
3106:
3093:
3050:
2954:
2752:
2578:
2146:
1003:
151:
98:
86:
2935:
469:. A graph can only contain a perfect matching when the graph has an even number of vertices.
306:
3155:
3141:
3079:
3071:
3016:
2979:
2946:
2904:
2876:
2791:
2744:
2667:
2568:
2564:
2546:
2503:
2429:
2323:
2217:
2126:
2084:
1972:
1953:
1922:
1906:
1902:
1828:
997:
522:
517:
501:
351:
146:
91:
3064:
2727:
2443:
2004:
421:. Thus, the size of a maximum matching is no larger than the size of a minimum edge cover:
3186:
3060:
2923:
2609:
2605:
2439:
2335:
2181:
2130:
1910:
1190:
1030:
62:
3120:
3004:
2712:
2531:
1239:
342:
3191:
3083:
2931:
2927:
2643:
2625:
2168:
states that, in bipartite graphs, the maximum matching is equal in size to the minimum
2138:
2134:
1937:
1760:
1630:
1326:
1306:
1286:
1266:
1219:
1099:
1079:
1056:
1036:
979:
894:
870:
31:
3144:(1987), "Fibonacci heaps and their uses in improved network optimization algorithms",
2190:
provides a characterization of bipartite graphs which have a perfect matching and the
3226:
2795:
2434:
2311:
2191:
1930:
1905:
to compute this quantity, even for bipartite graphs. It is also #P-complete to count
1653:
245:) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is
2394:
Alan
Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
1831:. A maximum matching is also a maximal matching, and hence it is possible to find a
413:. Every perfect matching is maximum and hence maximal. In some literature, the term
3169:
2893:
Tassa, Tamir (2012), "Finding all maximally-matchable edges in a bipartite graph",
2517:
2332:, a type of graph that can be used to model alternating path searches for matchings
2320:, the minimum number of edges to delete to prevent a perfect matching from existing
2240:
2169:
1926:
1898:
1892:
1612:
227:
122:
66:
38:
2679:
2344:, a set of vertices (rather than edges) no two of which are adjacent to each other
284:. The following figure shows examples of maximal matchings (red) in three graphs.
3124:
2338:, a matching in which no two elements prefer each other to their matched partners
848:{\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}
2271:
is about choosing minimum set of classes from given requirements for graduation.
2221:
2213:
1872:
1260:
1117:
103:
17:
2943:
Proceedings of the 22nd Annual ACM Symposium on Theory of
Computing (STOC 1990)
2613:
533:
In any graph without isolated vertices, the sum of the matching number and the
500:
is an alternating path that starts from and ends on free (unmatched) vertices.
289:
2909:
2880:
1879:
within factor 2 in polynomial time: simply find an arbitrary maximal matching
477:
418:
110:
3092:(second ed.), MIT Press and McGraw–Hill, Chapter 26, pp. 643–700,
2748:
2404:
2236:(in graph theoretical terms, a 6-vertex cycle) can be given such a structure.
2984:
2476:
1263:. Note that the (simple) graph of a real symmetric or skew-symmetric matrix
969:{\displaystyle \lambda _{1}>\lambda _{2}>\ldots >\lambda _{k}>0}
2756:
1660:
is used for this step, the running time of the
Hungarian algorithm becomes
3020:
2976:
Proceedings of the Forty-Third Annual ACM Symposium on Theory of
Computing
2950:
1180:{\displaystyle \pm \lambda _{1},\pm \lambda _{2},\ldots ,\pm \lambda _{k}}
3007:(1986), "On some solved and unsolved problems of chemical graph theory",
3160:
2508:
2326:, a matching in an edge-colored bipartite graph with no repeated colors
2233:
1968:
1868:
1569:. This problem has various algorithms for different classes of graphs.
2728:"Extremal problems for topological indices in combinatorial chemistry"
2671:
2574:
Computers and
Intractability: A Guide to the Theory of NP-Completeness
1858:
edges. Conversely, if we are given a minimum edge dominating set with
508:
is maximum if and only if there is no augmenting path with respect to
2550:
1871:; the decision versions of these problems are classical examples of
2480:
2258:
involves finding a minimum-weight perfect matching as a subproblem.
2703:
1611:, and algorithms for special classes of graphs such as bipartite
1365:-edge matchings in a graph is called a matching polynomial. Let
1323:
vertices and edges given by the nonozero off-diagonal entries of
1967:
The number of perfect matchings in a graph is also known as the
3049:, Annals of Discrete Mathematics, vol. 29, North-Holland,
2456:
Gallai, Tibor (1959), "Ăśber extreme Punkt- und Kantenmengen",
1699:, or the edge cost can be shifted with a potential to achieve
2695:
A combinatorial survey of identities for the double factorial
2243:
is the number of non-empty matchings plus one; it is used in
3217:
1216:
zeros, and (b) all real skew-symmetric matrices with graph
280:
has a non-empty intersection with at least one edge in
268:
that is not a subset of any other matching. A matching
2630:
The Complexity of Enumeration and Reliability Problems
2001:
For general graphs, a deterministic algorithm in time
2936:"An optimal algorithm for on-line bipartite matching"
2814:
2087:
2039:
2007:
1782:
1705:
1666:
1526:{\displaystyle \sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}
1455:
1393:
1329:
1309:
1289:
1269:
1242:
1222:
1193:
1125:
1102:
1082:
1059:
1039:
1006:
982:
917:
897:
873:
715:
645:
429:
365:
359:
to an edge of the matching. A matching is perfect if
309:
3193:
Fast Parallel Algorithms for Graph Matching Problems
2314:, a partition of the edges of a graph into matchings
1446:
Another definition gives the matching polynomial as
3126:
On Kuhn's Hungarian Method – A tribute from Hungary
2283:
problem involves bipartite matching as sub-problem.
1929:can be computed exactly in polynomial time via the
1897:The number of matchings in a graph is known as the
696:{\displaystyle |A\setminus B|\leq 2|B\setminus A|.}
3190:
2857:
2194:provides a characterization for arbitrary graphs.
2108:
2070:
2025:
1807:
1747:
1691:
1525:
1435:
1335:
1315:
1295:
1275:
1251:
1228:
1208:
1179:
1108:
1088:
1065:
1045:
1021:
988:
968:
903:
879:
847:
695:
459:
405:
324:
1925:states that the number of perfect matchings in a
1862:edges, we can construct a maximal matching with
1839:, that is, a maximal matching that contains the
1656:search in the augmenting path algorithm. If the
234:; that is, no two edges share common vertices.
1827:A maximal matching can be found with a simple
2865:algorithms for problems in matching theory",
2172:. Via this result, the minimum vertex cover,
1997:edges). Algorithms for this problem include:
1380:-edge matchings. One matching polynomial of
173:
8:
3132:(Technical report). Egerváry Research Group.
3111:: CS1 maint: multiple names: authors list (
2530:Yannakakis, Mihalis; Gavril, Fanica (1980),
2458:Ann. Univ. Sci. Budapest. Eötvös Sect. Math.
3179:Kekule Structures in Benzenoid Hydrocarbons
2277:involves bipartite matching as sub-problem.
3009:International Journal of Quantum Chemistry
2726:Tichy, Robert F.; Wagner, Stephan (2005),
1436:{\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}
180:
166:
71:
3159:
2983:
2908:
2844:
2836:
2816:
2815:
2813:
2785:
2702:
2661:
2507:
2477:https://doi.org/10.1016/j.laa.2016.02.004
2433:
2296:- a generalization of matching in graphs.
2086:
2059:
2041:
2040:
2038:
2006:
1793:
1781:
1728:
1716:
1704:
1677:
1665:
1505:
1495:
1485:
1460:
1454:
1424:
1414:
1398:
1392:
1328:
1308:
1288:
1268:
1241:
1221:
1192:
1171:
1149:
1133:
1124:
1101:
1081:
1058:
1038:
1005:
981:
954:
935:
922:
916:
896:
872:
837:
829:
818:
804:
793:
779:
768:
754:
746:
732:
724:
716:
714:
685:
671:
660:
646:
644:
584:. To see this, observe that each edge in
521:is a matching that is the edge set of an
428:
395:
390:
382:
374:
366:
364:
308:
2858:{\displaystyle {\widetilde {O}}(M(|V|))}
1576:, the optimization problem is to find a
594:can be adjacent to at most two edges in
2360:
2350:(also known as stable matching problem)
2071:{\displaystyle {\tilde {O}}(V^{2.376})}
1544:Algorithms and computational complexity
812:
762:
679:
654:
74:
3248:Computational problems in graph theory
3177:S. J. Cyvin & Ivan Gutman (1988),
3104:
2642:Bezáková, Ivona; Štefankovič, Daniel;
2230:Friedrich August Kekulé von Stradonitz
2216:consists of a perfect matching of its
2808:Cheriyan, Joseph (1997), "Randomized
2251:investigations for organic compounds.
2129:for matching was first considered by
1979:Finding all maximally matchable edges
1936:The number of perfect matchings in a
610:is a matching; moreover each edge in
7:
1615:, as described in the main article.
460:{\displaystyle \nu (G)\leq \rho (G)}
27:Set of edges without common vertices
2539:SIAM Journal on Applied Mathematics
2228:. These structures are named after
2033:and a randomized algorithm in time
1748:{\displaystyle O(V^{2}\log {V}+VE)}
1640:maximum weighted bipartite matching
1603:time, and there are more efficient
1073:if and only if (a) there is a real
30:For comparisons of two graphs, see
37:In the mathematical discipline of
25:
2632:, SIAM J. Comput., 8(3), 410–421
2736:Journal of Computational Biology
2532:"Edge dominating sets in graphs"
2481:https://arxiv.org/abs/1602.03590
2306:Dulmage–Mendelsohn decomposition
1580:. The problem is solved by the
560:are two maximal matchings, then
341:
288:
1875:problems. Both problems can be
2852:
2849:
2845:
2837:
2833:
2827:
2103:
2091:
2065:
2052:
2046:
2020:
2011:
1802:
1786:
1742:
1709:
1686:
1670:
1482:
1472:
838:
830:
819:
805:
794:
780:
769:
755:
747:
733:
725:
717:
686:
672:
661:
647:
454:
448:
439:
433:
391:
383:
375:
367:
319:
313:
76:Covering/packing-problem pairs
1:
2125:The problem of developing an
3189:and Wojciech Rytter (1998),
2896:Theoretical Computer Science
2796:10.1016/0196-6774(89)90005-9
2435:10.1016/0166-218X(92)90275-F
2421:Discrete Applied Mathematics
2373:NetworkX 2.8.2 documentation
2263:Matching in bipartite graphs
1768:non-bipartite weighted graph
1578:maximum cardinality matching
1557:Maximum cardinality matching
1551:Maximum-cardinality matching
276:is maximal if every edge in
3197:, Oxford University Press,
2606:Minimum Edge Dominating Set
2275:Hitchcock transport problem
2220:, showing the locations of
3264:
3238:Combinatorial optimization
3089:Introduction to Algorithms
2203:Matching in general graphs
2180:problems may be solved in
1982:
1890:
1843:possible number of edges.
1817:Edmonds' blossom algorithm
1622:
1574:unweighted bipartite graph
1563:combinatorial optimization
1554:
1350:
620:is adjacent to an edge in
29:
2910:10.1016/j.tcs.2011.12.071
2881:10.1137/S0097539793256223
2868:SIAM Journal on Computing
2649:SIAM Journal on Computing
2121:Online bipartite matching
1991:maximally matchable edges
1808:{\displaystyle O(V^{2}E)}
1692:{\displaystyle O(V^{2}E)}
1561:A fundamental problem in
406:{\displaystyle |M|=|V|/2}
230:edges, none of which are
3243:Polynomial-time problems
2749:10.1089/cmb.2005.12.1004
2610:Minimum Maximal Matching
1985:Maximally matchable edge
1913:, because computing the
1846:A maximal matching with
1837:minimum maximal matching
1609:approximation algorithms
1022:{\displaystyle 2k\leq n}
998:purely imaginary numbers
3233:Matching (graph theory)
2985:10.1145/1993636.1993716
2348:Stable marriage problem
2294:Matching in hypergraphs
2256:Chinese postman problem
2245:computational chemistry
2188:Hall's marriage theorem
2178:maximum vertex biclique
2174:maximum independent set
1776:can be solved in time
1773:maximum weight matching
1625:Maximum weight matching
1619:Maximum-weight matching
1582:Hopcroft-Karp algorithm
706:Further we deduce that
504:states that a matching
325:{\displaystyle \nu (G)}
128:Maximum independent set
2859:
2693:Callan, David (2009),
2342:Independent vertex set
2249:mathematical chemistry
2184:for bipartite graphs.
2110:
2109:{\displaystyle O(V+E)}
2072:
2027:
1952:even) is given by the
1809:
1755:running time with the
1749:
1693:
1658:Bellman–Ford algorithm
1527:
1437:
1337:
1317:
1297:
1277:
1253:
1230:
1210:
1181:
1110:
1090:
1067:
1047:
1023:
990:
970:
905:
881:
849:
697:
461:
407:
326:
3021:10.1002/qua.560300762
3003:; Klein, Douglas J.;
2951:10.1145/100216.100262
2860:
2773:Journal of Algorithms
2111:
2073:
2028:
2026:{\displaystyle O(VE)}
1810:
1750:
1694:
1605:randomized algorithms
1528:
1438:
1338:
1318:
1298:
1278:
1254:
1231:
1211:
1182:
1111:
1091:
1075:skew-symmetric matrix
1068:
1048:
1024:
991:
971:
906:
882:
850:
698:
474:near-perfect matching
462:
408:
327:
226:is a set of pairwise
3076:Charles E. Leiserson
2978:. pp. 597–606.
2945:. pp. 352–358.
2812:
2330:Skew-symmetric graph
2085:
2037:
2005:
1901:of the graph. It is
1780:
1703:
1664:
1453:
1391:
1347:Matching polynomials
1327:
1307:
1287:
1267:
1240:
1220:
1209:{\displaystyle n-2k}
1191:
1123:
1100:
1080:
1057:
1037:
1004:
980:
915:
895:
871:
713:
643:
535:edge covering number
427:
363:
307:
123:Minimum vertex cover
65:can be treated as a
47:independent edge set
3161:10.1145/28869.28874
2713:2009arXiv0906.1317C
2509:10.1145/28869.28874
2318:Matching preclusion
2300:Fractional matching
2281:Subtree isomorphism
1852:edge dominating set
1650:Hungarian algorithm
1359:generating function
1353:Matching polynomial
104:Maximum set packing
3147:Journal of the ACM
3138:Michael L. Fredman
2932:Vazirani, Vijay V.
2928:Vazirani, Umesh V.
2855:
2644:Vazirani, Vijay V.
2495:Journal of the ACM
2269:Graduation problem
2232:, who showed that
2226:chemical structure
2106:
2068:
2023:
1919:biadjacency matrix
1805:
1757:Dijkstra algorithm
1745:
1689:
1645:assignment problem
1523:
1471:
1433:
1409:
1333:
1313:
1293:
1273:
1252:{\displaystyle 2k}
1249:
1226:
1206:
1177:
1106:
1086:
1063:
1043:
1019:
986:
966:
901:
877:
845:
693:
457:
403:
322:
111:Minimum edge cover
3204:978-0-19-850162-6
3181:, Springer-Verlag
3001:Trinajstić, Nenad
2824:
2672:10.1137/050644033
2569:Johnson, David S.
2565:Garey, Michael R.
2214:aromatic compound
2161:Characterizations
2151:competitive ratio
2147:secretary problem
2049:
1962:telephone numbers
1907:perfect matchings
1887:Counting problems
1823:Maximal matchings
1770:, the problem of
1456:
1394:
1376:be the number of
1361:of the number of
1336:{\displaystyle A}
1316:{\displaystyle n}
1296:{\displaystyle n}
1276:{\displaystyle A}
1229:{\displaystyle G}
1109:{\displaystyle G}
1089:{\displaystyle A}
1066:{\displaystyle k}
1046:{\displaystyle G}
996:distinct nonzero
989:{\displaystyle k}
904:{\displaystyle n}
880:{\displaystyle G}
630:by maximality of
488:Given a matching
415:complete matching
190:
189:
157:
156:
152:Rectangle packing
99:Minimum set cover
87:Covering problems
49:in an undirected
16:(Redirected from
3255:
3207:
3196:
3182:
3173:
3163:
3142:Robert E. Tarjan
3133:
3131:
3116:
3110:
3102:
3080:Ronald L. Rivest
3072:Thomas H. Cormen
3067:
3025:
3023:
3015:(S20): 699–742,
2996:
2990:
2989:
2987:
2971:
2965:
2964:
2940:
2924:Karp, Richard M.
2920:
2914:
2913:
2912:
2890:
2884:
2883:
2875:(6): 1635–1655,
2864:
2862:
2861:
2856:
2848:
2840:
2826:
2825:
2817:
2805:
2799:
2798:
2789:
2767:
2761:
2759:
2743:(7): 1004–1013,
2732:
2723:
2717:
2715:
2706:
2690:
2684:
2683:
2665:
2656:(5): 1429–1454.
2639:
2633:
2623:
2617:
2603:
2595:
2589:
2587:
2577:, W.H. Freeman,
2561:
2555:
2553:
2536:
2527:
2521:
2520:
2511:
2489:
2483:
2473:
2467:
2465:
2453:
2447:
2446:
2437:
2415:
2409:
2408:
2401:
2395:
2392:
2386:
2385:
2380:
2379:
2365:
2324:Rainbow matching
2210:Kekulé structure
2156:
2127:online algorithm
2115:
2113:
2112:
2107:
2077:
2075:
2074:
2069:
2064:
2063:
2051:
2050:
2042:
2032:
2030:
2029:
2024:
1973:adjacency matrix
1954:double factorial
1911:bipartite graphs
1829:greedy algorithm
1814:
1812:
1811:
1806:
1798:
1797:
1754:
1752:
1751:
1746:
1732:
1721:
1720:
1698:
1696:
1695:
1690:
1682:
1681:
1636:bipartite graph,
1602:
1597:
1596:
1567:maximum matching
1532:
1530:
1529:
1524:
1519:
1518:
1500:
1499:
1490:
1489:
1470:
1442:
1440:
1439:
1434:
1429:
1428:
1419:
1418:
1408:
1342:
1340:
1339:
1334:
1322:
1320:
1319:
1314:
1302:
1300:
1299:
1294:
1282:
1280:
1279:
1274:
1258:
1256:
1255:
1250:
1235:
1233:
1232:
1227:
1215:
1213:
1212:
1207:
1186:
1184:
1183:
1178:
1176:
1175:
1154:
1153:
1138:
1137:
1115:
1113:
1112:
1107:
1095:
1093:
1092:
1087:
1072:
1070:
1069:
1064:
1052:
1050:
1049:
1044:
1028:
1026:
1025:
1020:
995:
993:
992:
987:
975:
973:
972:
967:
959:
958:
940:
939:
927:
926:
910:
908:
907:
902:
886:
884:
883:
878:
863:
854:
852:
851:
846:
841:
833:
822:
808:
797:
783:
772:
758:
750:
736:
728:
720:
702:
700:
699:
694:
689:
675:
664:
650:
635:
629:
619:
609:
603:
593:
583:
578:| ≤ 2|
571:
566:| ≤ 2|
559:
553:
544:
523:induced subgraph
518:induced matching
494:alternating path
468:
466:
464:
463:
458:
412:
410:
409:
404:
399:
394:
386:
378:
370:
352:perfect matching
345:
335:
331:
329:
328:
323:
298:maximum matching
292:
258:maximal matching
214:
182:
175:
168:
147:Polygon covering
116:Maximum matching
92:Packing problems
83:
82:
72:
21:
18:Maximal matching
3263:
3262:
3258:
3257:
3256:
3254:
3253:
3252:
3223:
3222:
3214:
3205:
3187:Marek Karpinski
3185:
3176:
3136:
3129:
3119:
3103:
3100:
3070:
3057:
3047:Matching Theory
3037:
3034:
3032:Further reading
3029:
3028:
2999:
2997:
2993:
2973:
2972:
2968:
2961:
2938:
2922:
2921:
2917:
2892:
2891:
2887:
2810:
2809:
2807:
2806:
2802:
2787:10.1.1.228.1996
2769:
2768:
2764:
2730:
2725:
2724:
2720:
2692:
2691:
2687:
2641:
2640:
2636:
2624:
2620:
2597:
2596:
2592:
2585:
2563:
2562:
2558:
2551:10.1137/0138030
2534:
2529:
2528:
2524:
2491:
2490:
2486:
2474:
2470:
2455:
2454:
2450:
2428:(1–3): 97–102,
2417:
2416:
2412:
2403:
2402:
2398:
2393:
2389:
2377:
2375:
2367:
2366:
2362:
2357:
2336:Stable matching
2290:
2265:
2218:carbon skeleton
2205:
2200:
2182:polynomial time
2166:KĹ‘nig's theorem
2163:
2154:
2131:Richard M. Karp
2123:
2083:
2082:
2055:
2035:
2034:
2003:
2002:
1987:
1981:
1947:
1895:
1889:
1825:
1789:
1778:
1777:
1712:
1701:
1700:
1673:
1662:
1661:
1627:
1621:
1600:
1595:
1592:
1590:
1588:
1585:
1559:
1553:
1546:
1501:
1491:
1481:
1451:
1450:
1420:
1410:
1389:
1388:
1374:
1369:be a graph and
1355:
1349:
1325:
1324:
1305:
1304:
1285:
1284:
1265:
1264:
1238:
1237:
1218:
1217:
1189:
1188:
1167:
1145:
1129:
1121:
1120:
1098:
1097:
1078:
1077:
1055:
1054:
1035:
1034:
1031:matching number
1002:
1001:
978:
977:
950:
931:
918:
913:
912:
893:
892:
869:
868:
859:
711:
710:
641:
640:
631:
621:
611:
605:
595:
585:
573:
561:
555:
549:
538:
531:
498:augmenting path
483:factor-critical
425:
424:
422:
361:
360:
333:
305:
304:
302:matching number
201:
195:
186:
63:bipartite graph
57:without common
35:
28:
23:
22:
15:
12:
11:
5:
3261:
3259:
3251:
3250:
3245:
3240:
3235:
3225:
3224:
3221:
3220:
3213:
3212:External links
3210:
3209:
3208:
3203:
3183:
3174:
3154:(3): 595–615,
3134:
3117:
3098:
3084:Clifford Stein
3068:
3055:
3043:Plummer, M. D.
3039:Lovász, László
3033:
3030:
3027:
3026:
2991:
2966:
2959:
2915:
2885:
2854:
2851:
2847:
2843:
2839:
2835:
2832:
2829:
2823:
2820:
2800:
2780:(4): 557–567,
2762:
2718:
2685:
2634:
2626:Leslie Valiant
2618:
2614:web compendium
2590:
2583:
2556:
2545:(3): 364–372,
2522:
2502:(3): 596–615,
2484:
2468:
2448:
2410:
2396:
2387:
2359:
2358:
2356:
2353:
2352:
2351:
2345:
2339:
2333:
2327:
2321:
2315:
2309:
2303:
2297:
2289:
2286:
2285:
2284:
2278:
2272:
2264:
2261:
2260:
2259:
2252:
2237:
2204:
2201:
2199:
2196:
2162:
2159:
2139:Vijay Vazirani
2135:Umesh Vazirani
2122:
2119:
2118:
2117:
2105:
2102:
2099:
2096:
2093:
2090:
2079:
2067:
2062:
2058:
2054:
2048:
2045:
2022:
2019:
2016:
2013:
2010:
1983:Main article:
1980:
1977:
1943:
1938:complete graph
1891:Main article:
1888:
1885:
1824:
1821:
1804:
1801:
1796:
1792:
1788:
1785:
1761:Fibonacci heap
1744:
1741:
1738:
1735:
1731:
1727:
1724:
1719:
1715:
1711:
1708:
1688:
1685:
1680:
1676:
1672:
1669:
1623:Main article:
1620:
1617:
1598:
1593:
1586:
1555:Main article:
1552:
1549:
1545:
1542:
1534:
1533:
1522:
1517:
1514:
1511:
1508:
1504:
1498:
1494:
1488:
1484:
1480:
1477:
1474:
1469:
1466:
1463:
1459:
1444:
1443:
1432:
1427:
1423:
1417:
1413:
1407:
1404:
1401:
1397:
1372:
1351:Main article:
1348:
1345:
1332:
1312:
1292:
1272:
1248:
1245:
1225:
1205:
1202:
1199:
1196:
1174:
1170:
1166:
1163:
1160:
1157:
1152:
1148:
1144:
1141:
1136:
1132:
1128:
1105:
1085:
1062:
1042:
1018:
1015:
1012:
1009:
985:
965:
962:
957:
953:
949:
946:
943:
938:
934:
930:
925:
921:
911:vertices, and
900:
876:
856:
855:
844:
840:
836:
832:
828:
825:
821:
817:
814:
811:
807:
803:
800:
796:
792:
789:
786:
782:
778:
775:
771:
767:
764:
761:
757:
753:
749:
745:
742:
739:
735:
731:
727:
723:
719:
704:
703:
692:
688:
684:
681:
678:
674:
670:
667:
663:
659:
656:
653:
649:
530:
527:
456:
453:
450:
447:
444:
441:
438:
435:
432:
402:
398:
393:
389:
385:
381:
377:
373:
369:
347:
346:
321:
318:
315:
312:
294:
293:
260:is a matching
194:
191:
188:
187:
185:
184:
177:
170:
162:
159:
158:
155:
154:
149:
143:
142:
137:
131:
130:
125:
119:
118:
113:
107:
106:
101:
95:
94:
89:
79:
78:
32:Graph matching
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
3260:
3249:
3246:
3244:
3241:
3239:
3236:
3234:
3231:
3230:
3228:
3219:
3216:
3215:
3211:
3206:
3200:
3195:
3194:
3188:
3184:
3180:
3175:
3171:
3167:
3162:
3157:
3153:
3149:
3148:
3143:
3139:
3135:
3128:
3127:
3122:
3118:
3114:
3108:
3101:
3099:0-262-53196-8
3095:
3091:
3090:
3085:
3081:
3077:
3073:
3069:
3066:
3062:
3058:
3056:0-444-87916-1
3052:
3048:
3044:
3040:
3036:
3035:
3031:
3022:
3018:
3014:
3010:
3006:
3005:Randić, Milan
3002:
2995:
2992:
2986:
2981:
2977:
2970:
2967:
2962:
2960:0-89791-361-2
2956:
2952:
2948:
2944:
2937:
2933:
2929:
2925:
2919:
2916:
2911:
2906:
2902:
2898:
2897:
2889:
2886:
2882:
2878:
2874:
2870:
2869:
2841:
2830:
2821:
2818:
2804:
2801:
2797:
2793:
2788:
2783:
2779:
2775:
2774:
2766:
2763:
2758:
2754:
2750:
2746:
2742:
2738:
2737:
2729:
2722:
2719:
2714:
2710:
2705:
2700:
2696:
2689:
2686:
2681:
2677:
2673:
2669:
2664:
2663:10.1.1.80.687
2659:
2655:
2651:
2650:
2645:
2638:
2635:
2631:
2627:
2622:
2619:
2615:
2611:
2607:
2601:
2594:
2591:
2586:
2584:0-7167-1045-5
2580:
2576:
2575:
2570:
2566:
2560:
2557:
2552:
2548:
2544:
2540:
2533:
2526:
2523:
2519:
2515:
2510:
2505:
2501:
2497:
2496:
2488:
2485:
2482:
2478:
2472:
2469:
2463:
2459:
2452:
2449:
2445:
2441:
2436:
2431:
2427:
2423:
2422:
2414:
2411:
2406:
2400:
2397:
2391:
2388:
2384:
2374:
2370:
2369:"is_matching"
2364:
2361:
2354:
2349:
2346:
2343:
2340:
2337:
2334:
2331:
2328:
2325:
2322:
2319:
2316:
2313:
2312:Edge coloring
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2291:
2287:
2282:
2279:
2276:
2273:
2270:
2267:
2266:
2262:
2257:
2253:
2250:
2246:
2242:
2238:
2235:
2231:
2227:
2223:
2219:
2215:
2211:
2207:
2206:
2202:
2197:
2195:
2193:
2192:Tutte theorem
2189:
2185:
2183:
2179:
2175:
2171:
2167:
2160:
2158:
2152:
2148:
2142:
2140:
2136:
2132:
2128:
2120:
2100:
2097:
2094:
2088:
2080:
2060:
2056:
2043:
2017:
2014:
2008:
2000:
1999:
1998:
1996:
1992:
1986:
1978:
1976:
1974:
1970:
1965:
1963:
1959:
1955:
1951:
1946:
1942:
1939:
1934:
1932:
1931:FKT algorithm
1928:
1924:
1920:
1916:
1912:
1908:
1904:
1900:
1894:
1886:
1884:
1882:
1878:
1874:
1870:
1865:
1861:
1857:
1853:
1849:
1844:
1842:
1838:
1834:
1830:
1822:
1820:
1818:
1799:
1794:
1790:
1783:
1775:
1774:
1769:
1764:
1762:
1758:
1739:
1736:
1733:
1729:
1725:
1722:
1717:
1713:
1706:
1683:
1678:
1674:
1667:
1659:
1655:
1654:shortest path
1651:
1647:
1646:
1641:
1637:
1634:
1633:
1626:
1618:
1616:
1614:
1613:planar graphs
1610:
1606:
1583:
1579:
1575:
1570:
1568:
1565:is finding a
1564:
1558:
1550:
1548:
1543:
1541:
1539:
1520:
1515:
1512:
1509:
1506:
1502:
1496:
1492:
1486:
1478:
1475:
1467:
1464:
1461:
1457:
1449:
1448:
1447:
1430:
1425:
1421:
1415:
1411:
1405:
1402:
1399:
1395:
1387:
1386:
1385:
1383:
1379:
1375:
1368:
1364:
1360:
1354:
1346:
1344:
1330:
1310:
1290:
1270:
1262:
1246:
1243:
1236:have at most
1223:
1203:
1200:
1197:
1194:
1172:
1168:
1164:
1161:
1158:
1155:
1150:
1146:
1142:
1139:
1134:
1130:
1126:
1119:
1103:
1083:
1076:
1060:
1040:
1032:
1016:
1013:
1010:
1007:
999:
983:
963:
960:
955:
951:
947:
944:
941:
936:
932:
928:
923:
919:
898:
890:
874:
865:
862:
842:
834:
826:
823:
815:
809:
801:
798:
790:
787:
784:
776:
773:
765:
759:
751:
743:
740:
737:
729:
721:
709:
708:
707:
690:
682:
676:
668:
665:
657:
651:
639:
638:
637:
634:
628:
625: \
624:
618:
615: \
614:
608:
602:
599: \
598:
592:
589: \
588:
581:
577:
569:
565:
558:
552:
546:
542:
536:
528:
526:
524:
520:
519:
513:
511:
507:
503:
502:Berge's lemma
499:
495:
491:
486:
484:
479:
475:
470:
451:
445:
442:
436:
430:
420:
416:
400:
396:
387:
379:
371:
358:
354:
353:
344:
340:
339:
338:
316:
310:
303:
299:
291:
287:
286:
285:
283:
279:
275:
271:
267:
263:
259:
254:
252:
248:
244:
240:
235:
233:
229:
225:
221:
218:
212:
208:
204:
200:
192:
183:
178:
176:
171:
169:
164:
163:
161:
160:
153:
150:
148:
145:
144:
141:
138:
136:
133:
132:
129:
126:
124:
121:
120:
117:
114:
112:
109:
108:
105:
102:
100:
97:
96:
93:
90:
88:
85:
84:
81:
80:
77:
73:
70:
68:
64:
60:
56:
52:
48:
44:
40:
33:
19:
3192:
3178:
3151:
3145:
3125:
3121:András Frank
3088:
3046:
3012:
3008:
2994:
2975:
2969:
2942:
2918:
2900:
2894:
2888:
2872:
2866:
2803:
2777:
2771:
2765:
2740:
2734:
2721:
2694:
2688:
2653:
2647:
2637:
2629:
2621:
2599:
2593:
2573:
2559:
2542:
2538:
2525:
2499:
2493:
2487:
2471:
2461:
2457:
2451:
2425:
2419:
2413:
2399:
2390:
2382:
2376:. Retrieved
2372:
2363:
2241:Hosoya index
2222:double bonds
2209:
2198:Applications
2186:
2170:vertex cover
2164:
2143:
2124:
1994:
1988:
1966:
1957:
1949:
1944:
1940:
1935:
1927:planar graph
1899:Hosoya index
1896:
1893:Hosoya index
1880:
1877:approximated
1863:
1859:
1855:
1850:edges is an
1847:
1845:
1840:
1836:
1832:
1826:
1771:
1767:
1765:
1643:
1639:
1635:
1631:
1628:
1573:
1571:
1566:
1560:
1547:
1537:
1535:
1445:
1381:
1377:
1370:
1366:
1362:
1356:
866:
860:
857:
705:
632:
626:
622:
616:
612:
606:
600:
596:
590:
586:
579:
575:
567:
563:
556:
550:
547:
540:
532:
516:
514:
509:
505:
497:
493:
489:
487:
473:
471:
414:
350:
348:
301:
297:
295:
281:
277:
273:
269:
265:
261:
257:
255:
250:
246:
242:
238:
237:A vertex is
236:
228:non-adjacent
223:
219:
216:
210:
206:
202:
196:
135:Bin covering
115:
67:network flow
53:is a set of
46:
42:
39:graph theory
36:
2998:See, e.g.,
1903:#P-complete
1873:NP-complete
1261:eigenvalues
1118:eigenvalues
1096:with graph
1029:. Then the
332:of a graph
272:of a graph
264:of a graph
251:unsaturated
193:Definitions
140:Bin packing
3227:Categories
2602:, Springer
2378:2022-05-31
2355:References
2141:in 1990.
1909:, even in
529:Properties
478:odd number
419:edge cover
2903:: 50–58,
2822:~
2782:CiteSeerX
2704:0906.1317
2658:CiteSeerX
2464:: 133–138
2405:"Preview"
2047:~
1923:Kasteleyn
1915:permanent
1726:
1642:, or the
1510:−
1476:−
1465:≥
1458:∑
1403:≥
1396:∑
1283:of order
1198:−
1169:λ
1165:±
1159:…
1147:λ
1143:±
1131:λ
1127:±
1014:≤
952:λ
945:…
933:λ
920:λ
813:∖
788:∩
774:≤
763:∖
741:∩
680:∖
666:≤
655:∖
446:ρ
443:≤
431:ν
311:ν
247:unmatched
243:saturated
69:problem.
3123:(2004).
3107:citation
3086:(2001),
3045:(1986),
2934:(1990).
2757:16201918
2571:(1979),
2288:See also
1841:smallest
1632:weighted
1584:in time
1259:nonzero
636:, hence
604:because
357:incident
217:matching
209:,
197:Given a
59:vertices
43:matching
3170:7904683
3065:0859549
2709:Bibcode
2612:in the
2518:7904683
2444:1011265
2234:benzene
2224:in the
1995:allowed
1971:of its
1969:hafnian
1869:NP-hard
1833:largest
1591:√
467:
423:
239:matched
3201:
3168:
3096:
3063:
3053:
2957:
2784:
2755:
2680:755231
2678:
2660:
2581:
2516:
2442:
2212:of an
2176:, and
2137:, and
1948:(with
1815:using
1648:. The
1572:In an
1536:where
1000:where
3166:S2CID
3130:(PDF)
2939:(PDF)
2731:(PDF)
2699:arXiv
2676:S2CID
2535:(PDF)
2514:S2CID
2155:0.696
2061:2.376
1993:, or
1854:with
1766:In a
1629:In a
1116:and
889:graph
887:be a
543:| / 2
492:, an
232:loops
199:graph
55:edges
51:graph
3199:ISBN
3140:and
3113:link
3094:ISBN
3082:and
3051:ISBN
2955:ISBN
2753:PMID
2608:and
2579:ISBN
2254:The
2247:and
2239:The
1759:and
1303:has
1187:and
961:>
948:>
942:>
929:>
572:and
554:and
249:(or
241:(or
41:, a
3156:doi
3017:doi
2980:doi
2947:doi
2905:doi
2901:423
2877:doi
2792:doi
2745:doi
2668:doi
2547:doi
2504:doi
2430:doi
2153:of
1723:log
1384:is
1053:is
1033:of
976:be
891:on
548:If
515:An
253:).
222:in
205:= (
45:or
3229::
3164:,
3152:34
3150:,
3109:}}
3105:{{
3078:,
3074:,
3061:MR
3059:,
3041:;
3013:30
3011:,
2953:.
2941:.
2930:;
2926:;
2899:,
2873:26
2871:,
2790:,
2778:10
2776:,
2751:,
2741:12
2739:,
2733:,
2707:,
2697:,
2674:.
2666:.
2654:37
2652:.
2628:,
2567:;
2543:38
2541:,
2537:,
2512:,
2500:34
2498:,
2479:,
2460:,
2440:MR
2438:,
2426:24
2424:,
2381:.
2371:.
2208:A
2157:.
2133:,
1975:.
1964:.
1933:.
1883:.
1819:.
1763:.
1607:,
1357:A
1343:.
545:.
525:.
512:.
485:.
472:A
349:A
296:A
256:A
215:a
213:),
3172:.
3158::
3115:)
3024:.
3019::
2988:.
2982::
2963:.
2949::
2907::
2879::
2853:)
2850:)
2846:|
2842:V
2838:|
2834:(
2831:M
2828:(
2819:O
2794::
2760:.
2747::
2716:.
2711::
2701::
2682:.
2670::
2616:.
2554:.
2549::
2506::
2466:.
2462:2
2432::
2407:.
2302:.
2116:.
2104:)
2101:E
2098:+
2095:V
2092:(
2089:O
2078:.
2066:)
2057:V
2053:(
2044:O
2021:)
2018:E
2015:V
2012:(
2009:O
1958:n
1956:(
1950:n
1945:n
1941:K
1881:M
1864:k
1860:k
1856:k
1848:k
1803:)
1800:E
1795:2
1791:V
1787:(
1784:O
1743:)
1740:E
1737:V
1734:+
1730:V
1718:2
1714:V
1710:(
1707:O
1687:)
1684:E
1679:2
1675:V
1671:(
1668:O
1601:)
1599:E
1594:V
1589:(
1587:O
1538:n
1521:,
1516:k
1513:2
1507:n
1503:x
1497:k
1493:m
1487:k
1483:)
1479:1
1473:(
1468:0
1462:k
1431:.
1426:k
1422:x
1416:k
1412:m
1406:0
1400:k
1382:G
1378:k
1373:k
1371:m
1367:G
1363:k
1331:A
1311:n
1291:n
1271:A
1247:k
1244:2
1224:G
1204:k
1201:2
1195:n
1173:k
1162:,
1156:,
1151:2
1140:,
1135:1
1104:G
1084:A
1061:k
1041:G
1017:n
1011:k
1008:2
984:k
964:0
956:k
937:2
924:1
899:n
875:G
861:G
843:.
839:|
835:B
831:|
827:2
824:=
820:|
816:A
810:B
806:|
802:2
799:+
795:|
791:A
785:B
781:|
777:2
770:|
766:B
760:A
756:|
752:+
748:|
744:B
738:A
734:|
730:=
726:|
722:A
718:|
691:.
687:|
683:A
677:B
673:|
669:2
662:|
658:B
652:A
648:|
633:B
627:A
623:B
617:B
613:A
607:A
601:B
597:A
591:A
587:B
582:|
580:A
576:B
574:|
570:|
568:B
564:A
562:|
557:B
551:A
541:V
539:|
510:M
506:M
490:M
455:)
452:G
449:(
440:)
437:G
434:(
401:2
397:/
392:|
388:V
384:|
380:=
376:|
372:M
368:|
334:G
320:)
317:G
314:(
282:M
278:G
274:G
270:M
266:G
262:M
224:G
220:M
211:E
207:V
203:G
181:e
174:t
167:v
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
