| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429286 | Information Processing Letters | 2006 | 6 Pages |
Abstract
Flow network simplification can reduce the size of the flow network and hence the amount of computation performed by flow algorithms. We present the first linear time algorithm for the undirected network case. We also give an O(|E|∗(|V|+|E|)) time algorithm for the directed case, an improvement over the previous best O(|V|+2|E|log|V|) time solution. Both of our algorithms are quite simple.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
