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.
Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets / Acua, Vicente; Birmel, Etienne; Cottret, Ludovic; Crescenzi, Pierluigi; Jourdan, Fabien; Lacroix, Vincent; MARCHETTI SPACCAMELA, Alberto; Marino, Andrea; Milreu, Paulo Vieira; Sagot, Marie France; Stougie, Leen. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 457:(2012), pp. 1-9. [10.1016/j.tcs.2012.07.023]
Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets
MARCHETTI SPACCAMELA, Alberto;
2012
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2012_11573-951164.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
335.05 kB
Formato
Adobe PDF
|
335.05 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
