A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract)
Jünger, Michael and Lee, Eva K. and Mutzel, Petra and Odenthal, Thomas (1998) A Polyhedral Approach to the Multi-Layer Crossing Minimization Problem (Extended Abstract). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 13-24 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_46).
Full text not available from this repository.
We study the multi-layer crossing minimization problem from a polyhedral point of view. After the introduction of an integer programming formulation of the multi-layer crossing minimization problem, we examine the 2-layer case and derive several classes of facets of the associated polytope. Preliminary computational results for 2- and 3-layer instances indicate, that the usage of the corresponding facet-defining inequalities in a branch-and-cut approach may only lead to a practically useful algorithm, if deeper polyhedral studies are conducted.
Repository Staff Only: item control page