Computing Minimum-Weight Perfect Matchings

References

• Aho A. V., Hopcroft J. E., Ullman J. D. On finding lowest common ancestors in trees. SIAM J. Comput. (1976) 5:115–132Crossref, Google Scholar
• Akl S. G. A note on euclidean matchings triangulations and spanning trees. J. Combinatorics, Inform. System Sci. (1983) 8:175–180Google Scholar
• Applegate D., Cook W., Johnson D. S., McGeoch C. C. Solving large-scale matching problems. Network Flows and Matching: First DIMACS Implementation Challenge (1993) (American Mathematical Society, Providence, RI) 557–576Crossref, Google Scholar
• Asano T., Edahiro M., Imai H., Iri M., Murota K., Toussaint G. T. Practical use of bucketing techniques in computational geometry. Computational Geometry (1985) (North Holland, Amsterdam) 153–195Crossref, Google Scholar
• Atamtürk A. Efficient algorithms for the minimum cost perfect matching problem on general graphs. (1993) (Bilkent University, Turkey) . Master of Science ThesisGoogle Scholar
• Avis D. A survey of heuristics for the weighted matching problem. Networks (1983) 13:475–493Crossref, Google Scholar
• Ball M. O., Bodin L. D., Dial R. A matching based heuristic for scheduling mass transit crews and vehicles. Transportation Sci. (1983) 17:4–31Link, Google Scholar
• Ball M. O., Derigs U. An analysis of alternative strategies for implementing matching algorithms. Networks (1983) 13:517–549Crossref, Google Scholar
• Bell C. E. Weighted matching with vertex weights: An application to scheduling training sessions in NASA space shuttle cockpit simulators. Eur. J. Oper. Res. (1994) 73:443–449Crossref, Google Scholar
• Bentley J. Software exploratorium: Some random thoughts. Unix Review (1992) 10:71–77(Computer code available via anonymous ftp at ftp://dimacs.rutgers.edu/pub/netflow/generators/universal.c)Google Scholar
• Bentley J. L. Fast algorithms for geometric traveling salesman problems. ORSA J. Comput. (1992) 4:387–411Link, Google Scholar
• Burkard R. E., Derigs U.Assignment and Matching Problems: Solution Methods with FORTRAN-Programs (1980) (Springer Lecture). Notes in Mathematical Systems 184Crossref, Google Scholar
• Cook W. J., Cunningham W. H., Pulleyblank W. R., Schrijver A.Combinatorial Optimization (1998) (Wiley, New York) Google Scholar
• Cunningham W. H., Marsh A. B. A primal algorithm for optimum matching. Math. Programming Stud. (1978) 8:50–72Crossref, Google Scholar
• Derigs U. A shortest augmenting path method for solving minimal perfect matching problems. Networks (1981) 11:379–390Crossref, Google Scholar
• Derigs U. Solving large-scale matching problems efficiently: A new primal matching approach. Networks (1986) 16:1–16Crossref, Google Scholar
• Derigs U. Solving non-bipartite matching problems via shortest path techniques. Ann. Oper. Res. (1988) 13:225–261Crossref, Google Scholar
• Derigs U., Metz A. On the use of optimal fractional matchings for solving the (integer) matching problem. Computing (1986) 36:263–270Crossref, Google Scholar
• Derigs U., Metz A. Solving (large scale) matching problems combinatorially. Math. Programming (1991) 50:113–122Crossref, Google Scholar
• Derigs U., Metz A. A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints. Oper. Res. Spektrum (1992) 14:91–106Crossref, Google Scholar
• Dillencourt M. B. Toughness and delaunay triangulations. Discrete Comput. Geometry (1990) 5:575–601Crossref, Google Scholar
• Edmonds J. Maximum matching and a polyhedron with 0, 1-vertices. J. Res. National Bureau of Standards (1965) 69B:125–130Crossref, Google Scholar
• Edmonds J. Paths trees and flowers. Canadian J. Math. (1965) 17:449–467Crossref, Google Scholar
• Edmonds J., Johnson E. L., Lockhart S. C. Blossom I: A computer code for the matching problem. (1969) (IBM T. J. Watson Research Center, Yorktown Heights, New York) . Unpublished reportGoogle Scholar
• Fortune S. J. A sweepline algorithm for voronoi diagrams. Algorithmica (1987) 2:153–174Crossref, Google Scholar
• Fortune S. J.“Sweep2” computer code available via anonymous ftp from http://netlib.att.comGoogle Scholar
• Gabow H. N.Implementation of Algorithms for Maximum Matching on Nonbipartite Graphs (1974) (Stanford University). Ph.D. thesisGoogle Scholar
• Gabow H. N. A scaling algorithm for weighted matching on general graphs. (1985) Proc. 26th Annual Sympos. Foundations Comput. Sci.(IEEE Computer Society, Los Angeles) 90–100Crossref, Google Scholar
• Gabow H. N. Data structures for weighted matching and nearest common ancestors with linking. Proc. First Annual ACM-SIAM Sympos. Discrete Algorithms (1990) (Association for Computing Machinery, New York) 434–443Google Scholar
• Gabow H. N., Galil Z., Spencer T. H. Efficient implementation of graph algorithms using contraction. J. ACM (1989) 36:540–572Crossref, Google Scholar
• Gabow H. N., Tarjan R. E. Faster scaling algorithms for general graph matching problems. J. ACM (1991) 38:815–853Crossref, Google Scholar
• Galil Z. Efficient algorithms for finding maximum matchings in graphs. ACM Comput. Surveys (1986) 18:23–38Crossref, Google Scholar
• Galil Z., Micali S., Gabow H. N. An O(EV log V) algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. (1986) 15:120–130Crossref, Google Scholar
• Gerards A. M. H., Ball M. O., Magnanti T. L., Monma C. L., Nemhauser G. L. Matching. Network Models (1995) (North Holland, Amsterdam)Google Scholar
• Gerngross P. Zur implementation von edmonds' matching algorithmus: Datenstrukturen und Verschiedene Varianten. (1991) (Diplomarbeit, Institut für Mathematik, Universität Augsburg)Google Scholar
• Goemans M. X., Williamson D. P. A general approximation technique for constrained forest problems. SIAM J. Comput. (1995) 24:296–317Crossref, Google Scholar
• Grötschel M., Holland O. Solving matching problems with linear programming. Math. Programming (1985) 33:243–259Crossref, Google Scholar
• Havel T. F.The Combinatorial Distance Geometry Approach to the Calculation of Molecular Conformation (1982) (Biophysics Program, University of California, Berkeley) . Ph.D. thesisGoogle Scholar
• Imielinska C., Kalantari B. A generalized hypergreedy algorithm for weighted perfect matching. BIT (1993) 33:178–189Crossref, Google Scholar
• Iri M., Murota K., Matsui S. Heuristics for planar minimum-weight perfect matchings. Networks (1983) 13:67–92Crossref, Google Scholar
• Johnson D. S., McGeoch C. C.Network Flows and Matching—First DIMACS Implementation Challenge (1993) (American Mathematical Society, Providence, RI) Crossref, Google Scholar
• Johnson D. S., McGeoch L. A., Rothberg E. E. Asymptotic experimental analysis for the held-karp traveling salesman bound. (1996) Proc. Seventh Annual ACMS-IAM Sympos. Discrete Algorithms(Association for Computing Machinery, New York) 341–350Google Scholar
• Jünger M., pulleyblank W. New primal and dual matching heuristics. Algorithmica (1995) 13:357–380Crossref, Google Scholar
• Kazakidis G. Die lösung minimaler perfekter matchingprobleme mitte ls kürzester erweiternder pfade. (1980) (Diplomarbeit, Mathematiches Institut der Universität Köln)Google Scholar
• Kernighan B. W., Ritchie D. M.The C Programming Language (1978) (Prentice-Hall, Englewood Cliffs, New Jersey) Google Scholar
• Knuth D. E.Seminumerical Algorithms—The Art of Computer Programming (1969) 2(Addison-Wesley, Reading)Google Scholar
• Lawler E. L.Combinatorial Optimization: Networks and Matroids (1976) (Holt, Rinehart and Winston, New York)Google Scholar
• Lessard R., Rousseau J.-M., Minoux M. A new algorithm for general matching problems using network flow subproblems. Networks (1989) 19:459–479Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Lovász L., Plummer M. D.Matching Theory (1986) (Akadémia i Kiadoó, Budapest) Google Scholar
• Minoux M. A new polynomial cutting-plane algorithm for maximum weight matchings in general graphs, publication number 302, Centre de recherche sur les transports. (1983) (Université de Montréal)Google Scholar
• Miller D. L., Pekny J. F. A staged primal-dual algorithm for perfect b-matching with edge capacities. ORSA J. Comput. (1995) 7:298–320Link, Google Scholar
• Ólafsson S. Weighted matching in chess tournaments. J. Oper. Res. Soc. (1990) 41:17–24Crossref, Google Scholar
• Papadimitriou C. H. The probabilistic analysis of matching heuristics. (1977) Proc. 15th Annual Allerton Conf. Comm. Control, and Comput.:368–378Google Scholar
• Pulleyblank W. R.Faces of Matching Polyhedra (1973) (University of Waterloo, Waterloo, Ontario) . Ph.D. thesisGoogle Scholar
• Reingold E. M., Tarjan R. E. On a greedy heuristic for complete matching. SIAM J. Comput. (1981) 10:676–681Crossref, Google Scholar
• Reinelt G. TSPLIB95. Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR) (1995) . Heidelberg. (Manuscript and problem instances available at http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html)Google Scholar
• Riskin E. A., Ladner R., Wang R.-Y., Atlas L. E. Index assignment for progressive transmission of full-search vector quantization. IEEE Trans. Image Processing (1994) 3:307–312Crossref, Google Scholar
• Rohe A. Parallele heuristiken für sehr große traveling salesman probleme. (1997) (Diplomarbeit Research Institute for Discrete Mathematics, Universität Bonn)Google Scholar
• Shewchuk J. R. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. First Workshop on Applied Computational Geometry (1996) (Association for Computing Machinery, New York) 124–133(computer code available at http://www.cs.cmu.edu/quake/triangle.html)Google Scholar
• Tarjan R. E.Data Structures and Network Algorithms (1983) (SIAM, Philadelphia) Crossref, Google Scholar
• Trick M.Networks with Additional Structured Constraints (1987) (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia) . Ph.D. thesisGoogle Scholar
• Williamson D. P., Goemans M. X. Computational experience with an approximation algorithm on large-scale Euclidean matching instances. INFORMS J. Comput. (1996) 8:29–40Link, Google Scholar
• Weber G. M. Sensitivity analysis of optimal matchings. Networks (1981) 11:41–56Crossref, Google Scholar
• Weber M., Liebling T. M. Euclidean matching problems and the metropolis algorithm. Zeitschrift für Oper. Res. (1986) 30:A85–A110Google Scholar