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, V., Birmel, E., Cottret, L., Crescenzi, P., Jourdan, F., Lacroix, V., MARCHETTI SPACCAMELA, A., Marino, A., Milreu, P.V., Sagot, M.F., Stougie, L.. - 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.
