Abstract
Maximum Matching Problem on Bipartite Graph (MMPBG) has attracted attentions because of its intuitive nature and its wide applicability. The best time efficiency for it is O(Vn- m) up to date, which is obtained through reducing it to Maximum Flow problem and using Dinic's Maximum Flow algorithm. There exist three popular Maximum Flow algorithms: Dinic's, Karzanov's, and Goldberg-Trajan's. Two techniques used among popular Maximum Flow algorithms are layered network and preflow scheme. Both Dinic's and Karzanov's algorithms use layered network technique. In contrast, GoldbergTrajan's Maximum Flow algorithm uses preflow technique, which has not been applied to MMPBG yet. This research is, therefore, to study the effect of applying Goldberg-Trajan to MMPBG and to explore the possibility of improving the time efficiency for MMPBG. The direct application of Goldberg-Trajan's Maximum Flow algorithm yields the time efficiency 0(n3) for MMPBG. Both Push and Lift operations dominate the time efficiency. A modified Goldberg-Trajan's Maximum Flow algorithm is developed to improve the time efficiency. The analysis shows that time consumed on Push operation with the new algorithm is reduced from 0(n2m) to 0(n2). The time efficiency is dominated by Lift operation only with the new algorithm. In addition, the improvement on calls to Lift operations will improve the time efficiency for Push operations. The properties of a bipartite graph are further explored to improve the time efficiency. Some properties found in this research, such as four generic layers and maximum excess flow value of 1, are crucial to improve the algorithm on MMPBG.The results from this research show that the application of preflow method to NMPBG is perspective. Even though the preliminary results algorithm, it demonstrates its simplicity, and its possibility of improvement. Several aspects have been suggested for the improvement by analyzing the results of this research. The perspective time efficiency will be 0(n 2).
Yang, Bencai (1997). Some observations on Goldberg-Trajan's Maximum Flow algorithm on Bipartite Graphs. Master's thesis, Texas A&M University. Available electronically from
https : / /hdl .handle .net /1969 .1 /ETD -TAMU -1997 -THESIS -Y132.