Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets.

V. Acuna, E. Birmel, P. Vieira Milreu, L. Cottret, F. Jourdan, P. Crescenzi, M. Lacroix, A. Marino, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph G. In this version, we enumerate maximal DAGs whose sources and targets belong to a predefined subset of the nodes. We call such DAGs stories. We first show how to compute one story in polynomial-time, and then describe two different algorithms to "tell" all possible stories. © 2012 Elsevier B.V. All rights reserved.
Original languageEnglish
Pages (from-to)1-9
JournalTheoretical Computer Science
Volume457
Issue number26
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets.'. Together they form a unique fingerprint.

Cite this