Efficient Algorithms for Simplifying Flow Networks

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.