@inproceedings{b0b32f857d93448796770ce1af54f7cd,
title = "A branch-and-cut approach to the directed acyclic graph layering problem",
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 branch-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.",
author = "Patrick Healy and Nikolov, {Nikola S.}",
year = "2002",
doi = "10.1007/3-540-36151-0_10",
language = "English",
isbn = "3540001581",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "98--109",
editor = "Goodrich, {Michael T.} and Kobourov, {Stephen G.}",
booktitle = "Graph Drawing - 10th International Symposium, GD 2002, Revised Papers",
note = "10th International Symposium on Graph Drawing, GD 2002 ; Conference date: 26-08-2002 Through 28-08-2002",
}