| Type of Document |
Master's Thesis |
| Author |
Misiolek, Ewa
|
| Author's Email Address |
misiolek.2@nd.edu |
| URN |
etd-12042003-102851 |
| Title |
EFFICIENT ALGORITHMS FOR SIMPLIFYING FLOW NETWORKS |
| Degree |
Master of Science in Computer Science and Engineering |
| Department |
Computer Science and Engineering |
| Advisory Committee |
| Advisor Name |
Title |
| Danny Z. Chen |
Committee Chair |
| Aaron Striegel |
Committee Member |
| Menelaos Karavelas |
Committee Member |
|
| Keywords |
|
| Date of Defense |
2003-11-25 |
| Availability |
restricted |
Abstract
Computing maximum flow in a flow network is one of the important areas of research with many practical applications. In order to reduce the amount of work done by maximum flow algorithms, we want to detect and remove from the network all edges that have no impact on the maximum flow. In this thesis, we present several algorithms for removing such edges. In the case of undirected networks we give what we believe is the first such algorithm. For the directed case we improve on the previously known results.
|
| Files |
| Filename |
Size |
Approximate Download Time
(Hours:Minutes:Seconds)
|
| 28.8 Modem |
56K Modem |
ISDN (64 Kb) |
ISDN (128 Kb) |
Higher-speed Access |
![[campus]](/ETD-db/images/restricted.gif) |
MisiolekE12052003.pdf |
621.44 Kb |
00:02:52 |
00:01:28 |
00:01:17 |
00:00:38 |
00:00:03 |
indicates that a file or directory is
accessible from the campus network only.
|
