A Branch-and-Cut Approach to the Directed Acyclic Graph Layering Problem
Healy, Patrick and Nikolov, Nikola S. (2002) A Branch-and-Cut Approach to the Directed Acyclic Graph Layering Problem. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 98-109 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_10).
Full text not available from this repository.
We consider the problem of layering Directed Acyclic Graphs, an NP-hard problem. We show that some useful variants of the problem are also NP-hard. We provide an Integer Linear Programming formulation of a generalization of the standard problem and discuss how a banch-and-bound algorithm could be improved upon with cutting planes. We then describe a separation algorithm for two classes of valid inequalities that we have identified - one of which is facet-defining - and discuss their efficacy.
Repository Staff Only: item control page