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 , pp. 98-109(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_10).

Full text not available from this repository.

Abstract

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.

Item Type:	Conference Paper
Additional Information:	10.1007/3-540-36151-0_10
Classifications:	M Methods > M.999 Others G Algorithms and Complexity > G.700 Layering G Algorithms and Complexity > G.999 Others
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/207

Actions (login required)

View Item