A bibliography of graph matching (exact, heuristic, and approximation algoritms) and related topics such as min-cost flows, T-joins, b-matching, f-factors, and transportation.

Agarwal, Varadarajan. A near-linear constant-factor approximation for Euclidean bipartite matching? PDF
Ahuja, Orlin. A fast algorithm for the bipartite node weighted matching problem on path graphs with application to the inverse spanning tree problem. PDF
Alt, Blum, Mehlhorn, Paul. Computing a maximum cardinality matching in a bipartite graph in time O(..). PDF
Arjomandi. An efficient algorithm for coloring the edges of a graph with Delta+1 colors. PDF
Avis. Worst case bounds for the Euclidean matching problem. PDF
Avis. A survey of heuristics for the weighted matching problem. PDF
Avis. Two greedy heuristics for the weighted matching problem. PDF

Balinski. Establishing the matching polytope. PDF
Balinski, Gomory. A primal method for the assignment and transportation problems. PDF
Balinski. Labelling to obtain a maximum matching. PDF
Balinski. Signature methods for the assignment problem. PDF
Ball, Derigs. An analysis of alternative strategies for implementing matching algorithms. PDF
Bartnik. Algorithmes de Couplage dans les Graphes [in French]. PDF
Bayati, Shah, Sharma. Max-product for maximum weight matching: convergence, correctness and LP duality. PDF
Beckmann, Koopmans. A note on the optimal assignment problem (Cowles Commission Report). PDF
Beckmann, Koopmans. On some assignment problems (Cowles Commission Report). PDF
Berge. Two theorems in graph theory. PDF
Bertsekas. A new algorithm for the assignment problem. PDF
Bertsekas, Eckstein. Dual coordinate step methods for linear network flow problems. PDF
Bertsekas. Auction algorithms for network flow problems: a tutorial introduction. PDF
Birkhoff. Tres observaciones sobre el algebra lineal. PDF
Blum. A new approach to maximum matching in general graphs. (1990) PDF
Blum. Maximum matching in general graphs without explicit consideration of blossoms. (1999) PDF
Blum. Maximum matching in general graphs without explicit consideration of blossoms revisited. (2015) PDF
Brogden. An approach to the problem of differential prediction. PDF
Brown, von Neumann. Solutions of games by differential equations. PDF

Chandrasekaran, Vegh, Vempala. The cutting plane method is polynomial for perfect matchings. PDF
Cheng, Neely, Chugg. Iterative message passing algorithm for bipartite maximum weighted matching. PDF
Cheriyan. Randomized O(..) algorithms for problems in matching theory. PDF
Cheriyan, Mehlhorn. Algorithms for dense graphs and networks on the random access computer. PDF
Cook. A minimal totally dual integral system for the b-matching polyhedron. PDF
Cowles Monograph 13: Activity Analysis of Production and Allocation. PDF
Cunningham, Marsh. A primal algorithm for optimum matching. PDF
Cygan, Gabow, Sankowski. Algorithmic applications of Baur-Strassen's Theorem: Shortest cycles, diameter, and matching. PDF

Dantzig. Application of the simplex method to a transportation problem. PDF
Desler, Hakimi. A graph-theoretic approach to a class of integer-programming problems. PDF
Di, Lingas. Near approximation of maximum weight matching through efficient weight reduction. PDF
Dinic, Kronrod. An algorithm for the solution of the assignment problem [in English]. PDF
Dinic. Two assignment problems [in Russian]. PDF
Drake, Hougardy. A linear time approximation algorithm for weighted matchings in graphs. Journal , Conf
Duan, Pettie. Approximating maximum weight matching in near-linear time. PDF
Duan, Pettie, Su. Scaling algorithms for approximate and exact maximum weight matching. PDF
Duan, Su. A scaling algorithm for maximum weight matching in bipartite graphs. PDF
Dwyer. Solution of the personnel classification problem with the method of optimal regions. PDF
Dwyer, Galler. The method of reduced matrices for a general transportation problem. PDF
Dwyer. The direct solution of the transportation problem with reduced matrices. PDF

Easterfield. A combinatorial algorithm. Original , Republished
Edmonds, Johnson. Matching: a well-solved class of integer linear programs. PDF
Edmonds, Johnson. Matching, Euler tours, and the chinese postman. PDF
Edmonds. Maximum matching and a polyhedron with 0,1 vertices. PDF
Edmonds. Paths, trees, and flowers. PDF
Edmonds. An Introduction to Matching (Lecture Notes). Univ. of Michigan Summer School 1967. PDF
Edmonds, Karp. Theoretical improvements in algorithmic efficiency for network flow problems. PDF
Even, Kariv. An .. algorithm for maximum matching in general graphs. PDF

Feder, Motwani. Clique partitions, graph compression and speeding-up algorithms. PDF
Flood. On the Hitchcock distribution problem. PDF
Ford, Fulkerson. A simple algorithm for finding maximal network flows and an application to the Hitchcock problem. PDF
Fredman, Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. PDF
Fremuth-Paeger, Jungnickel. Balanced Network Flow I , II , III , IV , V , VI , VII , VIII
Fulkerson. An out-of-kilter method for minimal-cost flow problems. PDF

Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. Conf , TR
Gabow. An efficient implementation of Edmonds' algorithm for maximum matching on graphs. PDF
Gabow. Data structures for weighted matching and nearest common ancestors with linking. PDF
Gabow. Scaling algorithms for network problems. PDF
Gabow. A scaling algorithm for weighted matching on general graphs. PDF
Gabow, Nishizeki, Kariv, Leven, Terada. Algorithms for edge-coloring graphs. PDF
Gabow, Galil, Spencer. Efficient implementation of graph algorithms using contraction. PDF
Gabow, Tarjan. Almost optimum speed-ups of algorithms for bipartite matching and related problems. PDF
Gabow, Tarjan. Faster scaling algorithms for network problems. PDF
Gabow, Tarjan. Faster scaling algorithms for general graph-matching problems. PDF
Gale, Shapley. College admissions and the stability of marriage. PDF
Galil. Efficient algorithms for finding maximum matching in graphs. PDF
Galil, Micali, Gabow. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. PDF
Gallai. Maximum-minimum Saetze ueber Graphen [in German]. PDF
Galler, Dwyer. Translating the method of reduced matrices to machines. PDF
Gerards. Matching. PDF
Gleyzal. An algorithm for solving the transportation problem. PDF
Goemans, Williamson. A general approximation technique for constrained forest problems. PDF
Goldberg, Karzanov. Maximum skew-symmetric flows and matchings. PDF
Goldberg, Kennedy. An efficient cost scaling algorithm for the assignment problem. PDF
Goldberg, Kennedy. Global price updates help. PDF
Goldman. Optimal matchings and degree constrained subgraphs. PDF

Hadlock. Finding a maximum cut of a planar graph in polynomial time. PDF
Hanke, Hougardy. New approximation algorithms for the weighted matching problem. PDF
Hanke. Zwei approximative Algorithmen fuer das Matchingproblem in gewichteten Graphen [PhD thesis; in German]. PDF
Harris, Ross. Fundamentals of a method for evaluating rail net capacities [Rand research memorandum RM-1573]. PDF
Harvey. Algebraic algorithms for matching and matroid problems. PDF
Hitchcock. The distribution of a product from several sources to numerous localities. PDF
Hoffman, Markowitz. A note on shortest path, assignment, and transportation problems. PDF
Hopcroft, Karp. An .. algorithm for maximum matchings in bipartite graphs. PDF
Hougardy. Linear time approximation algorithms for degree constrained subgraph problems. PDF
Huang, Kavitha. Efficient algorithms for maximum weight matching in general graphs with small edge weights. PDF
Hung, Rom. Solving the assignment problem by relaxation. PDF

Ibarra, Moran. Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication. PDF
Indyk. A near linear time constant factor approximation for Euclidean dichromatic matching (cost). PDF
Iri, Murota, Matsui. Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane. PDF
Iri, Murota, Matsui. Heuristics for planar minimum-weight perfect matchings. PDF
Iri. A new method of solving transportation-network problems. PDF

Jacobi. De investigando ordine systematis aequationum differentialium vulgarium cujuscunque. English [translation due to Ollivier], Latin
Jacobi. De aequationum differentialium systemate non normali ad formam normalem revocando. English [translation due to Ollivier], Latin
Jonker, Volgenant. Teaching linear assignment by Mack's algorithm. PDF
Junger, Pulleyblank. New primal and dual matching heuristics. PDF

Kameda, Munro. A O(VE) algorithm for maximum matching of graphs. PDF
Kantorovitch. On the translocation of masses [in English]. PDF
Kao, Lam, Sung, Ting. A decomposition theorem for maximum weight bipartite matchings. PDF
Kariv. An .. algorithm for finding a maximum matching in a general graph. PDF
Karp, Upfal, Wigderson. Constructing a perfect matching is in random NC. PDF
Karzanov. [Finding matchings of a given weight; in Russian] PDF
Karzanov. [Cubic implementation of Edmonds' algorithm; in Russian] PDF
Karzanov. An exact estimate of an algorithm for finding a maximum flow, applied to the problem "on representatives" English , Russian
Karzanov. On finding maximum flow in a network with special structure and some applications. English , Russian
Kennedy. Solving unweighted and weighted bipartite matching problems in theory and practice [PhD thesis]. PDF
Klein. A primal method for minimal cost flows with applications to the assignment and transportation problems. PDF
Kocay, Stone. An algorithm for balanced flows. PDF
Koopmans, Beckmann. Assignment problems and the location of economic activities (Cowles Commission Report). PDF
Koopmans. Optimum utilization of the transportation system. PDF
Koopmans, Reiter. A model of transportation. PDF
Kosowsky, Yuille. The invisible hand algorithm: solving the assignment problem with statistical physics. PDF
Kuhn, Baumol. An approximative algorithm for the fixed-charges transportation problem. PDF
Kuhn. On combinatorial properties of matrices [English translation of Egervary]. PDF
Kuhn. The Hungarian method for the assignment problem. PDF
Kuhn. Variants of the Hungarian method for assignment problems. PDF
Kurtzburg. On approximation methods for the assignment problem. PDF
Kwan. Graphic programming using odd or even points. PDF

Lord. Notes on a problem of multiple classification. PDF
Lovasz. Subgraphs with prescribed valencies. PDF
Lovasz. On determinants, matchings, and random algorithms. PDF
Lur'e. [Algorithm for transportation by solving approximate optimal plans; in Russian] PDF
Lur'e. Methods of establishing the shortest running distances for freights on setting up transportation systems. PDF

Mack. The Bradford method for the assignment problem. PDF
Micali, Vazirani. An .. algorithm for finding maximum matching in general graphs. PDF
Motzkin. The assignment problem. PDF
Mucha. Finding maximum matchings via Gaussian elimination [PhD thesis]. PDF
Mucha, Sankowski. Maximum matchings via Gaussian elimination. PDF
Mucha, Sankowski. Maximum matchings in planar graphs via Gaussian elimination. PDF
Mueller-Hannemann, Schwartz. Implementing weighted b-matching algorithms. PDF
Munkres. Algorithms for the assignment and transportation problems. PDF

Norman, Rabin. An algorithm for a minimum cover of a graph. PDF

Orlin, Ahuja. New scaling algorithms for the assignment and minimum mean cycle problems. PDF
Orlova, Dorfman. Finding the maximum cut in a graph [English translation]. PDF

Papadimitriou. The probabilistic analysis of matching heuristics. PDF
Peterson, Loui. The general maximum matching algorithm of Micali and Vazirani. PDF
Pettie, Sanders. A simpler linear time 2/3 -eps approximation for maximum weight matching. PDF
Plummer. Graph factors and factorization: 1985-2003: A survey. PDF
Plummer. Matching theory - a sampler: from Denes Konig to the present. PDF
Preis. Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs. PDF
Pulleyblank. Faces of matching polyhedra. (University of Waterloo dissertation, 1973.) PDF

Rabin, Vazirani. Maximum matchings in general graphs through randomization. PDF
Ramshaw, Tarjan. A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs. PDF , Tech Report PDF
Reingold, Supowit. Probabilistic analysis of divide-and-conquer heuristics for minimum weighted Euclidean matching. PDF
Reingold, Tarjan. On a greedy heuristic for complete matching. PDF
Robinson. On the Hamiltonian game (a traveling salesman problem) [Rand Research Memorandum]. PDF

Sankowski. Maximum weight bipartite matching in matrix multiplication time. PDF
Sankowski. Algebraic graph algorithms. PDF
Shamir, Upfal. On factors in random graphs. PDF
Sharathkumar, Agarwal. Algorithms for the transportation problem in geometric settings. PDF
Sharathkumar, Agarwal. A near-linear time epsilon-approximation algorithm for bipartite geometric matching. PDF
Shiloach. Another look at the degree constrained subgraph problem. PDF
Supowit, Reingold, Plaisted. The traveling salesman problem and minimum matching in the unit square. PDF
Supowit. Heuristics for weighted perfect matching. PDF

Thorndike. The problem of classification of personnel. PDF
Tomizawa. On some techniques useful for solution of transportation network problems. PDF
Tornqvist. How to find optimal solutions to assignment problems (Cowles Commission Report). PDF
Tutte. The factorization of linear graphs. PDF
Tutte. Graph factors. PDF
Tutte. A short proof of the factor theorem for finite graphs. PDF
Tutte. Spanning subgraphs with specified valencies. PDF
Tutte. The factors of graphs. PDF

Urquhart. Degree constrained subgraphs of linear graphs. (University of Michigan dissertation, 1967.) PDF

Varadarajan, Agarwal. Approximation algorithms for bipartite and non-bipartite matching in the plane. PDF
Varadarajan. A divide-and-conquer algorithm for min-cost perfect matching in the plane. PDF
Vazirani. A theory of alternating paths and blossoms for proving correctness of the .. general graph maximum matching algorithm. (1994) PDF
Vazirani. A simplification of the MV matching algorithm and its proof. (2013) PDF
Vazirani. A proof of the MV matching algorithm. (2014) PDF
von Neumann. A certain zero-sum two-person game equivalent to the optimal assignment problem. PDF
Votaw. Methods of solving some personnel-classification problems. PDF
Votaw. Solution of the quota problem by a successive-reduction method. PDF
Votaw, Orden. The personnel assignment problem. PDF

White. A parametric study of matchings and coverings in weighted graphs. (University of Michigan dissertation, 1967.) PDF
Witzgall, Zahn. Modification of Edmonds' maximum matching algorithm. PDF