Networks · 2009 · 20 citations · 23 references
Natural SciencesComputer ScienceComputational GeometryOptimizationSeparation ProcessesCombinatorial OptimizationGraph AlgorithmsGraph TheoryBranch-and-cutValid Inequalities
Abstract In this article, we consider the k ‐edge connected subgraph problem from a polyhedral point of view. We introduce further classes of valid inequalities for the associated polytope and describe sufficient conditions for these inequalities to be facet defining. We also devise separation routines for these inequalities and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we develop a Branch‐and‐Cut algorithm and present some computational results. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010
23
A new approach to the maximum-flow problem
Andrew V. Goldberg, Robert E. Tarjan · Journal of the ACM · 1988 · 1.9K citations · Full text