On cardinality constrained cycle and path polytopes

• 成果类型: Article
• 署名作者: Kaibel, Volker; Stephan, Ruediger
• 署名单位: Otto von Guericke University; Technical University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0257-2
• 发表日期: 2010
• 页码: 371-394
• 关键词: facets

摘要

Given a directed graph D = (N, A) and a sequence of positive integers 1 = c(1) < c(2) < center dot center dot center dot < cm = |N|, we consider those path and cycle polytopes that are defined as the convex hulls of the incidence vectors simple paths and cycles of D of cardinality c(p) for some p is an element of {1, ..., m}, respectively. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. These inequalities can simply be transformed into inequalities that characterize the integer points of the undirected counterparts of cardinality constrained path and cycle polytopes. Beyond we investigate some further inequalities, in particular inequalities that are specific to odd/even paths and cycles.