Some observations on Goldberg-Trajan's Maximum Flow algorithm on Bipartite Graphs /
2).
| Main Author: | |
|---|---|
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
1997.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Summary: | 2). algorithm, it demonstrates its simplicity, and its algorithm. There exist three popular Maximum Flow algorithms: Dinic's, Karzanov's, and Goldberg-Trajan's. Two application of Goldberg-Trajan's Maximum Flow algorithm attracted attentions because of its intuitive nature and its bipartite graph are further explored to improve the time consumed on Push operation with the new algorithm is reduced contrast, GoldbergTrajan's Maximum Flow algorithm uses crucial to improve the algorithm on MMPBG.The results from efficiency for Push operations. The properties of a efficiency. Some properties found in this research, such as four generic layers and maximum excess flow value of 1, are from 0(n2m) to 0(n2). The time efficiency is dominated by Goldberg-Trajan to MMPBG and to explore the possibility of Goldberg-Trajan's Maximum Flow algorithm is developed to improve the time efficiency. The analysis shows that time improvement on calls to Lift operations will improve the time improving the time efficiency for MMPBG. The direct Karzanov's algorithms use layered network technique. In layered network and preflow scheme. Both Dinic's and Lift operation only with the new algorithm. In addition, the Lift operations dominate the time efficiency. A modified m) up to date, which is obtained through reducing it to Maximum Flow problem and using Dinic's Maximum Flow Maximum Matching Problem on Bipartite Graph (MMPBG) has NMPBG is perspective. Even though the preliminary results possibility of improvement. Several aspects have been preflow technique, which has not been applied to MMPBG yet. suggested for the improvement by analyzing the results of techniques used among popular Maximum Flow algorithms are This research is, therefore, to study the effect of applying this research show that the application of preflow method to this research. The perspective time efficiency will be 0(n wide applicability. The best time efficiency for it is O(Vn- yields the time efficiency 0(n3) for MMPBG. Both Push and |
|---|---|
| Item Description: | "Major subject: Computer Science". Vita. |
| Physical Description: | viii, 42 leaves : illustrations ; 28 cm. Also available online. Issued also on microfiche from Lange Micrographics. |
| Bibliography: | Includes bibliographical references: page 41. |