TY - JOUR
T1 - Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets.
AU - Acuna, V.
AU - Birmel, E.
AU - Vieira Milreu, P.
AU - Cottret, L.
AU - Jourdan, F.
AU - Crescenzi, P.
AU - Lacroix, M.
AU - Marino, A.
AU - Marchetti-Spaccamela, A.
AU - Sagot, M.-F.
AU - Stougie, L.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
U2 - 10.1016/j.tcs.2012.07.023
DO - 10.1016/j.tcs.2012.07.023
M3 - Article
VL - 457
SP - 1
EP - 9
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
IS - 26
ER -
