Stable sets and graphs with no even holes

• 成果类型: Article
• 署名作者: Conforti, Michele; Gerards, Bert; Pashkovich, Kanstantsin
• 署名单位: University of Padua; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0912-3
• 发表日期: 2015
• 页码: 13-39
• 关键词: consequences; algorithm; amalgam

摘要

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.