ISSN:
1436-4646
Keywords:
Graph
;
Matching
;
Branching
;
Linear Programming
;
Polyhedron
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Matching forests generalize branchings in a directed graph and matchings in an undirected graph. We present an efficient algorithm, the PMF Algorithm, for the problem: given a mixed graphG and a real weight on each of its edges, find a perfect matching forest of maximum weight-sum. The PMF Algorithm proves the sufficiency of a linear system which definesP = (G) andP(G), the convex hull of incidence vectors of perfect matching forests and matching forests respectively ofG. The algorithm also provides a generalization of Tutte's theorem on the existence of perfect matchings in an undirected graph.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581023
Permalink