A branch-and-cut approach to the directed acyclic graph layering problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publicationGraph Drawing - 10th International Symposium, GD 2002, Revised Papers
EditorsMichael T. Goodrich, Stephen G. Kobourov
PublisherSpringer Verlag
Pages98-109
Number of pages12
ISBN (Print)3540001581, 9783540001584
DOIs
Publication statusPublished - 2002
Event10th International Symposium on Graph Drawing, GD 2002 - Irvine, CA, United States
Duration: 26 Aug 200228 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2528 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Symposium on Graph Drawing, GD 2002
Country/TerritoryUnited States
CityIrvine, CA
Period26/08/0228/08/02

Fingerprint

Dive into the research topics of 'A branch-and-cut approach to the directed acyclic graph layering problem'. Together they form a unique fingerprint.

Cite this