Efficient enumeration of graph orientations with sources

DOI10.1016/j.dam.2017.08.002zbMath1390.05100OpenAlexW2747408003MaRDI QIDQ1647832

Andrea Marino, Romeo Rizzi, Alessio Conte, Roberto Grossi

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01609009/file/1-s2.0-S0166218X1730375X-main.pdf

zbMATH Keywords

delayenumerationacyclic orientationscyclic orientations

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Related Items

Criterion for a graph to admit a good orientation in terms of leaf blocks, Combinatorial Generation via Permutation Languages. V. Acyclic Orientations, Enumerating \(k\)-arc-connected orientations

Cites Work

• Generating all the acyclic orientations of an undirected graph
• \(G\)-parking functions, acyclic orientations and spanning trees
• Orientations with single source and sink
• On generating all maximal independent sets
• Colorings and orientations of graphs
• On enumerating all minimal solutions of feedback problems
• The number of dependent arcs in an acyclic orientation
• A note on finding the bridges of a graph
• Reverse search for enumeration
• Acyclic orientations of graphs
• Enumerating Cyclic Orientations of a Graph
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Directing Road Networks by Listing Strong Orientations
• Network reliability and acyclic orientations
• Finding an Unknown Acyclic Orientation of a Given Graph
• Hard Enumeration Problems in Geometry and Combinatorics
• Finding a Minimum Circuit in a Graph
• Generating the Acyclic Orientations of a Graph
• The acyclic orientation game on random graphs
• Nombre chromatique et plus longs chemins d'un graphe
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item