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

DOI10.1016/J.TCS.2012.07.023zbMATH Open1251.05079DBLPjournals/tcs/AcunaBCCJLMMMSS12OpenAlexW2114114129WikidataQ57265619 ScholiaQ57265619MaRDI QIDQ714835FDOQ714835

Authors: V. Acuña, Etienne Birmelé, Ludovic Cottret, Pilu Crescenzi, Fabien Jourdan, Vincent Lacroix, Alberto Marchetti-Spaccamela, Andrea Marino, Paulo Vieira Milreu, Marie-France Sagot, L. Stougie 

Publication date: 11 October 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.023

Recommendations

• Efficient coding of labeled directed acyclic graphs
• Counting acyclic orderings in directed acyclic graphs
• Random generation of essential directed acyclic graphs
• Random Generation of Directed Acyclic Graphs
• Analysis and enumeration. Algorithms for biological graphs

zbMATH Keywords

feedback arc setmaximal DAGmaximal directed acyclic graphsstory arc set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30)

Cites Work

• Computational aspects of monotone dualization: a brief survey
• On enumerating all minimal solutions of feedback problems

Cited In (2)

• Generating two-terminal directed acyclic graphs with a given complexity index by constraint logic programming
• Maximal Acyclic Subgraphs and Closest Stable Matrices

Uses Software

• MetExplore

This page was built for publication: Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714835)