Stable Sets and Graphs with no Even Holes
We develop decomposition/composition tools for efficiently solving maximum weight stable sets problems as well as for describing them as polynomially sized linear programs (using "compact systems"). Some of these are well-known but need some extra work to yield polynomial "decomposition schemes". We apply the tools to graphs with no even hole and no cap. A hole is a chordless cycle of length greater than three and a cap is a hole together with an additional node that is adjacent to two adjacent nodes of the hole and that has no other neighbors on the hole.
|Combinatorial optimization (msc 90C27)|
|Logistics (theme 3)|
|Organisation||Networks and Optimization|
Conforti, M, Gerards, A.M.H, & Pashkovich, K. (2013). Stable Sets and Graphs with no Even Holes.