Efficiently Computing Maximum Flows in Scale-Free Networks

Thomas Bläsius, Tobias Friedrich, Christopher Weyand

We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on…