A Branch-and-Cut Approach to the Directed Acyclic Graph Layering ProblemHealy, 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 , pp. 98-109(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_10). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3-540-36151-0_10
AbstractWe 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.
Actions (login required)
|