Efficient Algorithms for Simplifying Flow Networks

摘要：

Computing flows in a network is a fundamental graph theory problem with numerous applications. In this paper, we present two algorithms for simplifying a flow network G=(V, E), i.e., detecting and removing from G all edges (and vertices) that have no impact on any source-to-sink flow in G. Such network simplification can reduce the size of the network and hence the amount of computation performed by maximuM flow algorithms. For the undirected network case, we present the first linear time algorithm. For the directed network case, we present an O(|E| * (|V| + |E|)) time algorithm, an improvement over the previous best O(|V| + |E|2 log |V|) time solution. Both of our algorithms are quite simple.

作者: Ewa Misiolek Danny Z. Chen

作者单位: Mathematics Department, Saint Marys College, Notre Dame, IN 46556, USA Department of Computer Science and Engineering, University of Notre Dame Notre Dame, IN 46556, USA

会议类型: 国际会议

会议名称: The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)

会议地点: 昆明

会议语种:英文

页码: 737-746

在线出版日期: 2005-08-01（万方平台首次上网日期，不代表论文的发表时间）