Skip to main content
Log in

Optimum matching forests I: Special weights

  • Published:
Mathematical Programming Submit manuscript

Abstract

We introduce the concept of matching forests as a generalization of branchings in a directed graph and matchings in an undirected graph. Given special weights on the edges of a mixed graph, we present an efficient algorithm for finding an optimum weight-sum matching forest. The algorithm is a careful application of known branching and matching algorithms. The maximum cardinality matching forest problem is solved as a special case.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Berge,Graphs and hypergraphs (North-Holland, Amsterdam, 1973).

    Google Scholar 

  2. J. Edmonds, “Paths, trees and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467.

    Google Scholar 

  3. J. Edmonds, “Maximum matching and a polyhedron with (0, 1) vertices”,Journal of Research of the National Bureau of Standards 69B (1965) 125–130.

    Google Scholar 

  4. J. Edmonds, “An introduction to matching”, Lecture Notes, University of Michigan Summer Engineering Conference (1967).

  5. J. Edmonds, “Optimum branchings”,Journal of Research of the National Bureau of Standards 71B (1967) 233–240.

    Google Scholar 

  6. J. Edmonds and E.L. Johnson, “Matching: A well-solved class of integer linear programs”, in: R.K. Guy et al., eds,Combinatorial structures and their applications (Gordon and Breach; New York, 1970).

    Google Scholar 

  7. J. Edmonds and W.R. Pulleyblank,Optimum matching (John Hopkins Press, to appear).

  8. H.N. Gabow, “An efficient implementation of Edmonds' algorithm for maximum matchings on graphs”,Journal of the Association of Computing Machinery 23 (1976) 221–234.

    Google Scholar 

  9. R. Giles, “Optimum matching forests II: General weights”,Mathematical Programming 22 (1982) 12–38.

    Google Scholar 

  10. E.L. Lawler,Combinatorial optimization: Networks and matroids (Holt, Rinehart and Winston, New York, 1976).

    Google Scholar 

  11. W.R. Pulleyblank,Faces of matching polyhedra, Thesis, University of Waterloo, Canada (1973).

    Google Scholar 

  12. R.E. Tarjan, “Depth first search and linear graph algorithms”,SIAM Journal on Computing 1 (1972) 146–160.

    Google Scholar 

  13. R.E. Tarjan, “Finding optimum branchings”,Networks 7 (1977) 25–35.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Additional information

Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Giles, R. Optimum matching forests I: Special weights. Mathematical Programming 22, 1–11 (1982). https://doi.org/10.1007/BF01581022

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01581022

Key words

Navigation