A New Algorithm for Constructing A Maximum Matching on a Graph
Received:July 05, 1986  
Key Word:   
Fund ProjectL:
Author NameAffiliation
Dai Yiqi Tsinghua University
Beijing 
Hits: 1132
Download times: 664
Abstract:
      A new algorithm is proposed for constructing a maximum matching in a simple undirected graph.It uses DFS method and proper datastructure to find a alternating tree. In this way, the treatment of blosson and the determination of augme men ting path become very simple. The complexity of the algorithm is O(mn).
Citation:
DOI:10.3770/j.issn:1000-341X.1988.04.026
View Full Text  View/Add Comment  Download reader