J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Given a graph with n nodes each of them having labels equal either to 1 or 2 (a node with label 2 is called a terminal), we consider the (1,2)-survivable network design problem and more precisely, the separation problem for the partition inequalities. We show that this separation problem reduces to a sequence of submodular flow problems. Based on an algorithm developed by Fujishige and Zhang the problem is reduced to a sequence of O(n4) minimum cut problems. © 2004 Elsevier B.V. All rights reserved.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
David W. Jacobs, Daphna Weinshall, et al.
IEEE Transactions on Pattern Analysis and Machine Intelligence
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems