Matching problems in graphs
Mark Philip Thornton · Spiral (Imperial College London) · 1990
The 1-matching problem in a nondirected graph is the problem of choosing a subset of arcs which "pair" (or "match" ) the vertices of the graph.Each ver tex of the graph can at most be matched to one other vertex, or it can remain unmatched.The "cost" of a matching is the sum of the costs of the matching arcs, plus a "penalty cost" for each vertex remaining unmatched.The ob jective is to find the matching of minimum cost.This problem has practical applications in vehicle-routing problems, numerically controlled machining, computer plotting, etc.An efficient algorithm, for solving this problem, is developed in a series of stages starting from the overall concept, through to the complete algorithm.At each stage the necessity of the refinement is demonstrated, and its meaning, in terms of the original problem, is explained.The new concept of a Degree Penalised Matching (DPM) is introduced, and shown to be equivalent to the general Integer Programming problem.Although the general DPM problem is thus NP-complete, it is shown that a significant subset of DPM problems can be transformed, in polynomial time, into a 1-matching problem.A number of problem transformation methods are investigated to determine the applicability of this approach.An implementation for the 1-matching problem designed for sparse graphs is described, and its performance characteristics presented.A special test problem generator is developed to generate large sparse graphs (1500 ver tices, 7000 arcs) which have connectivity properties thought to be typical of real problems.The performance of the algorithms indicate that very large matching problems can be solved in reasonable computing time.To enable very large complete graphs to be managed, a graph ascent algo rithm is presented.This algorithm, based on the techniques of sub-gradient optimisation, is shown to be very effective in solving (exactly) random prob lems in the Euclidean plane.Its performance is orders of magnitude faster than other algorithms found in the literature.