Generating all the acyclic orientations of an undirected graph

DOI10.1016/S0020-0190(99)00120-9MaRDI QIDQ294704zbMATHWikidataFDO

Authors Valmir C. Barbosa, Jayme L. Szwarcfiter

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019099001209?np=y

zbMATH Keywords

graph algorithmsacyclic orientations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Generating the Acyclic Orientations of a Graph
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Enumerating cyclic orientations of a graph
• Efficient enumeration of graph orientations with sources
• scientific article; zbMATH DE number 4002122

Cites work

• scientific article; zbMATH DE number 784365 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Acyclic orientations of graphs
• Generating the Acyclic Orientations of a Graph
• Graph colorings and acyclic orientations

Cited in

(16)

• Enumerating cyclic orientations of a graph
• Enumerating \(k\)-arc-connected orientations
• On extensions, linear extensions, upsets and downsets of ordered sets
• Algorithms for media
• The size distribution for Markov equivalence classes of acyclic digraph models.
• Listing Acyclic Orientations of Graphs with Single and Multiple Sources
• Acyclic reorientation lattices and their lattice quotients
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• Acyclic reorientation lattices and their lattice quotients
• Efficient enumeration of graph orientations with sources
• A note on orientation and chromatic number of graphs
• Listing acyclic subgraphs and subgraphs of bounded girth in directed graphs
• FPT algorithms to enumerate and count acyclic and totally cyclic orientations
• A supernodal formulation of vertex colouring with applications in course timetabling
• Combinatorial Generation via Permutation Languages. V. Acyclic Orientations
• The representation of partially-concurrent open shop problems

This page was built for publication: Generating all the acyclic orientations of an undirected graph

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