Francisco Barahona, Stuart Bermon, et al.
Naval Research Logistics
We study the sparsest cut problem when the “capacity-demand” graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the “capacity-demand” graph has no K6 minor. We use ideas that had been developed for the max-cut problem, and show how to exploit the connections among these problems.
Francisco Barahona, Stuart Bermon, et al.
Naval Research Logistics
Mourad Baïou, Francisco Barahona
Operations Research Letters
Alan E. Rosenbluth, David O. Melville, et al.
SPIE Advanced Lithography 2009
Marcos Goycoolea, Alan T. Murray, et al.
Operations Research