Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Vicente Acuña; Etienne Birmelé; Ludovic Cottret; Pierluigi Crescenzi; Fabien Jourdan; Vincent Lacroix; Alberto Marchetti-Spaccamela; Andrea Marino; Paulo Vieira Milreu; Marie-France Sagot; Leen Stougie

doi:10.1016/j.tcs.2012.07.023

Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Vicente Acuña ^{1, 2} Etienne Birmelé ^{1, 3} Ludovic Cottret ⁴ Pierluigi Crescenzi ⁵ Fabien Jourdan ⁶ Vincent Lacroix ¹ Alberto Marchetti-Spaccamela ⁷ Andrea Marino ⁵ Paulo Vieira Milreu ¹ Marie-France Sagot ¹ Leen Stougie ^{8, 9}

1 BAMBOO - An algorithmic view on genomes, cells, and environments

Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive

2 Mathomics

3 SG - Laboratoire Statistique et Génome

4 LISBP - Laboratoire d'Ingénierie des Systèmes Biologiques et des Procédés

5 DSI - Dipartimento di Sistemi e Informatica

6 ToxAlim - ToxAlim

7 DIS - Dipartimento di Informatica e Sistemistica "Antonio Ruberti"

8 CWI - Centrum voor Wiskunde en Informatica

9 VU University Amsterdam

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 prede ned subset of the nodes. We call such DAGs stories. We rst show how to compute one story in polynomial-time, and then describe two di erent algorithms to \tell" all possible stories.

Keywords : Feedback arc set Maximal DAG Story arc set

Type de document :

Article dans une revue

Theoretical Computer Science, Elsevier, 2012, 457, pp.1--9. 〈10.1016/j.tcs.2012.07.023〉

Domaine :

Mathématiques [math] / Combinatoire [math.CO]

Informatique [cs] / Mathématique discrète [cs.DM]

Informatique [cs] / Algorithme et structure de données [cs.DS]

Liste complète des métadonnées

Littérature citée [5 références] Voir Masquer Télécharger

https://hal.inria.fr/hal-00764025
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 12 décembre 2012 - 11:05:57
Dernière modification le : mardi 20 novembre 2018 - 09:32:15
Document(s) archivé(s) le : dimanche 18 décembre 2016 - 00:12:48

stories.pdf

Fichiers produits par l'(les) auteur(s)

Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Fichier

Identifiants

Collections

Citation

Exporter

Métriques

857

275

Contact

Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Fichier

Identifiants

Collections

Citation

Exporter

Partager

Métriques

857

275

Contact