Back to Search Start Over

Facets in the Crossing Number Polytope

Authors :
Markus Chimani
Source :
SIAM Journal on Discrete Mathematics. 25:95-111
Publication Year :
2011
Publisher :
Society for Industrial & Applied Mathematics (SIAM), 2011.

Abstract

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.

Subjects

Subjects :
Discrete mathematics
Combinatorics
Constraint (information theory)
Rectification
General Mathematics
Core (graph theory)
Mathematics::Metric Geometry
Polytope
Crossing number (graph theory)
Integer programming
Mathematics

Details

ISSN :
10957146 and 08954801
Volume :
25
Database :
OpenAIRE
Journal :
SIAM Journal on Discrete Mathematics
Accession number :
edsair.doi...........35c92f36363a728ed50656e3d565346d
Full Text :
https://doi.org/10.1137/09076965x
Full Text Access
View/download PDF

Tools

Authors Abstract Subjects Details