| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
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
4
Pierluigi Crescenzi
5
Fabien Jourdan
6
Vincent Lacroix
1
Alberto Marchetti-Spaccamela
7
Andrea Marino
5
Paulo Vieira Milreu
1
Marie-France Sagot
1
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
Vicente Acuña 1, 2
Author Employer institution : Centre National de la Recherche Scientifique
Etienne Birmelé 1, 3
Mail :
Author Employer institution : Université d'Évry-Val-d'Essonne IdHAL : ebirmele IdRef : https://www.idref.fr/082335605
Ludovic Cottret 4
Author
Pierluigi Crescenzi 5
Author
Fabien Jourdan 6
Author
Vincent Lacroix 1
Mail :
Author Employer institution : Université Claude Bernard Lyon 1 IdHAL : vincent-lacroix ORCID : https://orcid.org/0000-0002-4235-8524
Alberto Marchetti-Spaccamela 7
Author
Andrea Marino 5
Author
Paulo Vieira Milreu 1
Author Employer institution : Institut National de Recherche en Informatique et en Automatique
Marie-France Sagot 1
Mail :
Author Employer institution : Institut National de Recherche en Informatique et en Automatique IdHAL : marie-france-sagot
Leen Stougie 8, 9
Author
1
BAMBOO - An algorithmic view on genomes, cells, and environments (Laboratoire de Biométrie et Biologie Évolutive. UMR CNRS 5558 Campus de La Doua - Université Claude Bernard - Lyon 1 Bâtiment Grégoire Mendel - 16 rue Raphael Dubois 69 100 Villeurbanne -- INRIA Grenoble - Rhône-Alpes Inovallée 655 avenue de l'Europe -Montbonnot 38 334 Saint Ismier Cedex France - France)
- Inria Grenoble - Rhône-Alpes (Inovallée
655 avenue de l'Europe
38330 Montbonnot - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (43 Bld du 11 Novembre 1918 69622 VILLEURBANNE CEDEX - France)
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France)
- Université de Lyon (92 rue Pasteur - CS 30122, 69361 Lyon Cedex 07 - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- VAS - VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (Université de Lyon, VetAgro Sup, 69280 Marcy l'Etoile (campus vétérinaire); Université de Clermont, VetAgro Sup, 63370 Lempdes (campus agronomique) - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5558 (France)
- UCBL - Université Claude Bernard Lyon 1 (43, boulevard du 11 novembre 1918, 69622 Villeurbanne cedex - France)
2
Mathomics (Center for Mathematical Modeling Center for Genome Regulation Blanco Encalada 2120, 6th floor, Santiago - Chile)
- University of Chile [Santiago] (Av. Libertador Bernardo O'Higgins 1058, Santiago de Chile - Chile)
3
SG - Laboratoire Statistique et Génome (23 boulevard de France 91 037 Évry, France - France)
- INRA - Institut National de la Recherche Agronomique (France)
- UEVE - Université d'Évry-Val-d'Essonne (Boulevard François Mitterrand 91025 Evry Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8071 (France)
4
LISBP - Laboratoire d'Ingénierie des Systèmes Biologiques et des Procédés (135 Avenue de rangueil 31077 Toulouse cedex 04 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5504 (France)
- INSA Toulouse - Institut National des Sciences Appliquées - Toulouse (135, avenue de Rangueil - 31077 Toulouse cedex 4 - France)
- INRA - Institut National de la Recherche Agronomique : UMR0792 (France)
5
DSI - Dipartimento di Sistemi e Informatica (Engineering Division Via di Santa Marta, 3 50139 Firenze - Italy - Italy)
- Università degli Studi di Firenze [Firenze] (Piazza di San Marco, 4, 50121 Firenze FI, Italie - Italy)
6
ToxAlim - ToxAlim (23 ch. Capelles 31076 TOULOUSE - France)
- UT3 - Université Toulouse III - Paul Sabatier (118 route de Narbonne - 31062 Toulouse - France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- Toulouse INP - Institut National Polytechnique (Toulouse) (France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- ENVT - Ecole Nationale Vétérinaire de Toulouse (23 chemin des Capelles
31076 Toulouse
Cedex - France)
- Toulouse INP - Institut National Polytechnique (Toulouse) (France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- Toulouse INP - Institut National Polytechnique (Toulouse) (France)
- INPT - EI Purpan - Ecole d'Ingénieurs de Purpan (France)
- Toulouse INP - Institut National Polytechnique (Toulouse) (France)
- Université Fédérale Toulouse Midi-Pyrénées (41 Allée Jules Guesde, 31000 Toulouse - France)
- Toulouse INP - Institut National Polytechnique (Toulouse) (France)
- INRA - Institut National de la Recherche Agronomique : UMR1331 (France)
7
DIS - Dipartimento di Informatica e Sistemistica "Antonio Ruberti" (Sapienza Università di Roma - Via Ariosto 25, 00185 Roma - Italy)
- Università degli Studi di Roma "La Sapienza" [Rome] (Piazzale Aldo Moro 5, 00185 Roma - Italy)
8
CWI - Centrum voor Wiskunde en Informatica (Kruislaan 413 P.O. Box 94079 1090 GB Amsterdam - Netherlands)
- CWI - Centrum Wiskunde & Informatica (Science Park 123, 1098 XG Amsterdam - Netherlands)
- Netherlands Organisation for Scientific Research (Netherlands)
9
VU University Amsterdam (De Boelelaan 1105, 1081 HV Amsterdam - Netherlands)
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.
Complete list of metadatas
https://hal.inria.fr/hal-00764025
Contributor : Marie-France Sagot <>
Submitted on : Wednesday, December 12, 2012 - 11:05:57 AM
Last modification on : Tuesday, March 17, 2020 - 2:52:56 AM
Document(s) archivé(s) le : Sunday, December 18, 2016 - 12:12:48 AM
Contributor : Marie-France Sagot <>
Submitted on : Wednesday, December 12, 2012 - 11:05:57 AM
Last modification on : Tuesday, March 17, 2020 - 2:52:56 AM
Document(s) archivé(s) le : Sunday, December 18, 2016 - 12:12:48 AM
File
stories.pdf
Files produced by the author(s)
Identifiers
- HAL Id : hal-00764025, version 1
- DOI : 10.1016/j.tcs.2012.07.023
Collections
CNRS | INRIA | UNIV-EVRY | INSMI | BAMBOO | BIOENVIS | INRA | TDS-MACS | INSA-TOULOUSE | UNIV-LYON1 | INSA-GROUPE | UNIV-TLSE3 | UDL | TBI
Citation
Vicente Acuña, Etienne Birmelé, Ludovic Cottret, Pierluigi Crescenzi, Fabien Jourdan, et al.. Telling stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets. Theoretical Computer Science, Elsevier, 2012, 457, pp.1--9. ⟨10.1016/j.tcs.2012.07.023⟩. ⟨hal-00764025⟩
Metrics
Record views
983
Files downloads