A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem
成果类型：
Article
署名作者：
Chandran, Bala G.; Hochbaum, Dorit S.
署名单位：
University of California System; University of California Berkeley; University of California System; University of California Berkeley
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1080.0572
发表日期：
2009
页码：
358-376
关键词：
摘要：
We present the results of a computational investigation of the pseudoflow and push-relabel algorithms for the maximum flow and minimum s-t cut problems. The two algorithms were tested on several problem instances from the literature. Our results show that our implementation of the pseudoflow algorithm is faster than the best-known implementation of push-relabel on most of the problem instances within our computational study.