Skip to main content
SpringerLink
Log in

Bestimmung eines maximalen Matching in beliebigen Graphen

Determination of a maximal matching in arbitrary graphs

  • Published:
Computing Aims and scope Submit manuscript

Zusammenfassung

Es wird ein Algorithmus zur Ermittlung eines maximalen Matching angegeben, dessen Vorteil darin besteht, daß er auf beliebige auch nichtpaare Graphen angewendet werden kann und ohne Schwierigkeiten auf einem Computer ausgeführt werden kann. Ein entsprechendes Programm wurde an verschiedenen Graphen getestet.

Summary

There are two advantages of the algorithm given in the paper: (I) It applies to bipartite as well as to nonbipartite graphs and (II) it is easy to implement it on a computer. A computer program based on the algorithm has been tested using various graphs.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Literatur

  1. Berge, C.: The Theory of Graphs. London: J. Wiley. 1962.

    Google Scholar 

  2. Busacker, R. G., undTh. L. Saaty: Endliche Graphen und Netzwerke. München: Oldenbourg. 1968.

    Google Scholar 

  3. Edmonds, J.: Paths, trees and flowers. Canad. J.Math.17, 449–467 (1960).

    Google Scholar 

  4. Egerváry, E.: On Combinatorial Properties of Matrices. Office Naval Res. Logist Project Rept., Dpt. of Math., Princeton University. 1953.

  5. Ford, L. R., andFulkerson D. R.: Maximal flow through a network. Canad. J. Math9, 210–218 (1956).

    Google Scholar 

  6. Harary, F.: Graph Theory. London: Addison Wesley. 1969.

    Google Scholar 

  7. Kuhn, H. W.: The Hungarian method for solving the assignment problem. Naval. Res. Logist. Quart.3, 253–258 (1956).

    Google Scholar 

  8. Liu, C. L.: Introduction to Combinatorial Mathematics. New York: McGraw-Hill. 1968.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. 3. Institut für Mathematik, Technische Hochschule Wien, Karlsplatz 13, A-1040, Wien

    W. Dörfler

  2. Institut für Statistik und Informatik, Hochschule Linz, A-4045, Linz

    J. Mühlbacher

Authors
  1. W. Dörfler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Mühlbacher
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dörfler, W., Mühlbacher, J. Bestimmung eines maximalen Matching in beliebigen Graphen. Computing 9, 251–257 (1972). https://doi.org/10.1007/BF02246734

Download citation

  • Received:

  • Issue Date:

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

Search

Navigation