Efficient enumeration of graph orientations with sources

DOI10.1016/J.DAM.2017.08.002MaRDI QIDQ1647832zbMATH OpenOpenAlexFDO

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi

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)

Recommendations

• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Enumerating cyclic orientations of a graph
• Generating all the acyclic orientations of an undirected graph
• Enumerating \(k\)-arc-connected orientations
• Generating the Acyclic Orientations of a Graph

Cites work

• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• scientific article; zbMATH DE number 3215864 (Why is no real title available?)
• scientific article; zbMATH DE number 3248752 (Why is no real title available?)
• scientific article; zbMATH DE number 3303831 (Why is no real title available?)
• A note on finding the bridges of a graph
• Acyclic orientations of graphs
• Colorings and orientations of graphs
• Directing Road Networks by Listing Strong Orientations
• Enumerating cyclic orientations of a graph
• Finding a Minimum Circuit in a Graph
• Finding an unknown acyclic orientation of a given graph
• Generating all the acyclic orientations of an undirected graph
• Generating the Acyclic Orientations of a Graph
• Graph orientations and linear extensions
• Hard Enumeration Problems in Geometry and Combinatorics
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Network reliability and acyclic orientations
• Nombre chromatique et plus longs chemins d'un graphe
• On enumerating all minimal solutions of feedback problems
• On generating all maximal independent sets
• Orientations with single source and sink
• Reverse search for enumeration
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• The acyclic orientation game on random graphs
• The number of dependent arcs in an acyclic orientation
• \(G\)-parking functions, acyclic orientations and spanning trees

Cited in

(8)

• Orientations with single source and sink
• Criterion for a graph to admit a good orientation in terms of leaf blocks
• Enumerating cyclic orientations of a graph
• Enumerating \(k\)-arc-connected orientations
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
• Generating all the acyclic orientations of an undirected graph

This page was built for publication: Efficient enumeration of graph orientations with sources

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