FACETS IN THE CROSSING NUMBER POLYTOPE

被引：2
|
作者：
Chimani, Markus [1 ]
机构：
[1] Univ Jena, Jena, Germany
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 01期
关键词：
crossing number; integer linear program; polyhedral study; facets; Kuratowski constraints;
D O I：
10.1137/09076965X
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In the last years, several integer linear programming (ILP) formulations for the crossing number problem arose. While they all contain a common conceptual core, the properties of the corresponding polytopes have never been investigated. In this paper, we formally establish the crossing number polytope and show several facet-defining constraint classes.
引用
收藏
页码：95 / 111
页数：17
相关论文
共 50 条
  • [1] The circuit polytope: Facets
    Bauer, P
    MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (01) : 110 - 145
  • [2] New facets of the STS polytope generated from known facets of the ATS polytope
    Balas, Egon
    Carr, Robert
    Fischetti, Matteo
    Simonetti, Neil
    DISCRETE OPTIMIZATION, 2006, 3 (01) : 3 - 19
  • [3] The facets of the spanning trees polytope
    Brahim Chaourar
    Mathematical Methods of Operations Research, 2022, 96 : 113 - 121
  • [4] The facets of the spanning trees polytope
    Chaourar, Brahim
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2022, 96 (01) : 113 - 121
  • [5] The facets of the polytope of modules of a graph
    Kieffer, Y
    OPERATIONS RESEARCH LETTERS, 2003, 31 (06) : 435 - 441
  • [6] New facets for the set packing polytope
    Cánovas, L
    Landete, M
    Marín, A
    OPERATIONS RESEARCH LETTERS, 2000, 27 (04) : 153 - 161
  • [7] Facets of the balanced minimal evolution polytope
    Forcey, Stefan
    Keefe, Logan
    Sands, William
    JOURNAL OF MATHEMATICAL BIOLOGY, 2016, 73 (02) : 447 - 468
  • [8] New facets of the linear ordering polytope
    Bolotashvili, G
    Kovalev, M
    Girlich, E
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (03) : 326 - 336
  • [9] Facets of the balanced minimal evolution polytope
    Stefan Forcey
    Logan Keefe
    William Sands
    Journal of Mathematical Biology, 2016, 73 : 447 - 468
  • [10] On the facets and diameter of the k-cycle polytope
    Girlich, Eberhard
    Hoeding, Michael
    Horbach, Andrei
    Kovalev, Mikhail
    OPTIMIZATION, 2006, 55 (04) : 311 - 339
12345