Department of Computer Science & Engineering

This report presents research into a fundamentally new approach to finding all pairwise minimum cuts in a network that can utilize optimality conditions other than those characterized by Mengers theorem or the max-flow min-cut theorem. The focus is on vertex degree domination, rather than construction of saturating paths. We have not been able to show a polynomial-time, deterministic algorithm of this kind, but the investigation has yielded many new insights into the structure of minimum cuts in a network and heuristics for discovering them.

Pre-2018 CSE ID: CS1999-0625