Abstract / Excerpt:

Objectives: To provide the reader with sufficient background to follow easily the proofs of the theorems, in as much as many of the details have been left out in the paper of Edmonds, (2) to discuss the following question : a. Under what conditions can a planted tree in a graph G blossom? b. When can blossom in G be shrunk? c. How is a flower formed in a blossomed tree? d. Under what conditions can a matching in a graph G be of maximum cardinality? (3) to discuss the matching algorithm, specifically the problem of finding a maximum matching in a graph using the concepts of alternating paths, trees, blossoms and flowers.
Methodology: This study interprets and discusses in detail the paper, "Paths, trees and flowers" by Jack Edmonds.
Conclusions: The degree of the vertex is computed and the vertices are sorted according to increasing degree. Starting from an initial empty matching, the matching is augmented along a maximal set of augmenting paths of length one. The alternating trees are grown simultaneously from different exposed vertices. An augmenting path is detected whenever two outer vertices out of two different trees are joined by an edge. H. Gabow conducted some experiments implementing Edmonds' algorithm for determining a maximum matching in a graph. The sum matching algorithm considers the sum of all the weights of the matching edges. Like the maximum cardinality matching algorithm, the basic operation in finding a maximum weight matching is the generation of an alternating tree and the existence of augmenting paths.

Info

Source Institution	Ateneo de Davao University
Unit	Natural Science
Authors	Maribbay, Agripina B.
Page Count	1
Place of Publication	Manila
Original Publication Date	March 1, 1983
Tags	Dissertations, Graph theory.

Preview