2015
Stable sets and graphs with no even holes
Publication
Publication
Mathematical Programming Series B , Volume 153 p. 13- 39
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.
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.
| Additional Metadata | |
|---|---|
| , , , | |
| Springer | |
| doi.org/10.1007/s10107-015-0912-3 | |
| Mathematical Programming Series B | |
| Organisation | Networks and Optimization |
|
Conforti, M., Gerards, B., & Pashkovich, K. (2015). Stable sets and graphs with no even holes. Mathematical Programming Series B, 153, 13–39. doi:10.1007/s10107-015-0912-3 |
|
| See Also |
|---|
techReport
|
techReport
|
techReport
|
techReport
|