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

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. PDF

Blum. Maximum matching in general graphs without explicit consideration of blossoms. 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, 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

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

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. 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