التفاصيل البيبلوغرافية
| العنوان: |
Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets |
| المؤلفون: |
Acuña, Vicente1,2,3 vicente.acuna@univ-lyon1.fr, Birmelé, Etienne1,2,4 etienne.birmele@genopole.cnrs.fr, Cottret, Ludovic5 cottret@insa-toulouse.fr, Crescenzi, Pierluigi6 pierluigi.crescenzi@unifi.it, Jourdan, Fabien7 fjourdan@toulouse.inra.fr, Lacroix, Vincent1,2 vincent.lacroix@univ-lyon1.fr, Marchetti-Spaccamela, Alberto8 alberto@dis.uniroma1.it, Marino, Andrea6 andrea.marino@unifi.it, Milreu, Paulo Vieira1 pvmilreu@gmail.com, Sagot, Marie-France1,2 marie-France.sagot@inria.fr, Stougie, Leen9 l.stougie@vu.nl |
| المصدر: |
Theoretical Computer Science. Oct2012, Vol. 457, p1-9. 9p. |
| مصطلحات موضوعية: |
*SET theory, *DIRECTED acyclic graphs, *CONSTRAINT satisfaction, *POLYNOMIALS, *ALGORITHMS, *MATHEMATICAL analysis |
| مستخلص: |
Abstract: We present a constrained version of the problem of enumerating all maximal directed acyclic subgraphs (DAG) of a graph . 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. [Copyright &y& Elsevier] |
| قاعدة البيانات: |
Academic Search Index |
Full Text Finder