## A Branch-and-Cut Approach to the Directed Acyclic Graph Layering Problem
Healy, Patrick and Nikolov, Nikola S.
(2002)
Full text not available from this repository. ## 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.
Repository Staff Only: item control page References |