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.

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
ID Code:207

Repository Staff Only: item control page

References

O. Bastert and C. Matuszewski. Layered drawings of digraphs. In M. Kaufmann and D. Wagner, editors, Drawing Graphs: Method and Models, volume 2025 of LNCS, pages 87-120. Springer-Verlag, 2000.

J. Branke, S. Leppert, M. Middendorf, and P. Eades. Width-restricted layering of acyclic digraphs with consideration of dummy nodes. Information Processing Letters, 81(2):59-63, January 2002.

P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information Processing, 13(4):424-437, 1990.

P. Healy and N.S. Nikolov. How to layer a directed acyclic graph. In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing: Proceedings of 9th International Symposium, GD 2001, volume 2265 of LNCS, pages 16-30. Springer-Verlag, 2002.

P. Healy and N.S. Nikolov. Facets of the directed acyclic graph layering polytope. In Ludek Kucera, editor, Graph Theoretical Concepts in Computer Science: WG2002, LNCS. Springer-Verlag, (To appear.).

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transaction on Systems, Man, and Cybernetics, 11(2):109-125, February 1981.