Abstract
Given a directed graph (Formula presented.) , three positive integers (Formula presented.) , (Formula presented.) and (Formula presented.) , and a partition (Formula presented.) of (Formula presented.) such that there are no arcs from (Formula presented.) to (Formula presented.) when (Formula presented.) or (Formula presented.) , the set of direct arcs from (Formula presented.) to (Formula presented.) , (Formula presented.) , is called an (Formula presented.) -extended cut. Given a weight vector (Formula presented.) , we aim to compute a minimum-weight (Formula presented.) -extended cut. Some special vertices may be required to belong to a particular subset (Formula presented.). We study this problem, and for special cases we provide polynomial-time algorithms, linear formulations and polyhedral descriptions. We also review some NP-hard variants.
| Original language | English |
|---|---|
| Pages (from-to) | 1034-1044 |
| Number of pages | 11 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 31 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 Apr 2016 |
Keywords
- Compact formulation
- Cut
- Graph partitioning
- Polyhedra