Telling Stories

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.
Type de document :
Communication dans un congrès
ICALP 2011 satellite workshop: Graph Algorithms and Applications (GA), 2011, Zurich, Switzerland. 2011, 〈10.1016/j.tcs.2012.07.023〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00748788
Contributeur : Marie-France Sagot <>
Soumis le : mardi 6 novembre 2012 - 08:37:50
Dernière modification le : jeudi 28 juin 2018 - 14:37:01

Lien texte intégral

Identifiants

Collections

Citation

Vicente Acuña, Etienne Birmele, Ludovic Cottret, Pierluigi Crescenzi, Fabien Jourdan, et al.. Telling Stories. ICALP 2011 satellite workshop: Graph Algorithms and Applications (GA), 2011, Zurich, Switzerland. 2011, 〈10.1016/j.tcs.2012.07.023〉. 〈hal-00748788〉

Partager

Métriques

Consultations de la notice

459