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 - UMR 5558

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

Document type :

Journal articles

Domain :

Mathematics [math] / Combinatorics [math.CO]

Computer Science [cs] / Discrete Mathematics [cs.DM]

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Complete list of metadatas

Cited literature [5 references] Display Hide Download

https://hal.inria.fr/hal-00764025
Contributor : Marie-France Sagot <>
Submitted on : Wednesday, December 12, 2012 - 11:05:57 AM
Last modification on : Friday, January 10, 2020 - 9:09:57 PM
Long-term archiving on: Sunday, December 18, 2016 - 12:12:48 AM

stories.pdf

Files produced by the author(s)

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

File

Identifiers

Collections

Citation

Export

Metrics

967

486

Contact

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

File

Identifiers

Collections

Citation

Export

Share

Metrics

967

486

Contact