Generating all the acyclic orientations of an undirected graph

DOI10.1016/S0020-0190(99)00120-9zbMath1339.05379WikidataQ127548920 ScholiaQ127548920MaRDI QIDQ294704

Valmir C. Barbosa, Jayme Luiz 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

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

Related Items (11)

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

Cites Work

• Acyclic orientations of graphs
• Graph colorings and acyclic orientations
• Generating the Acyclic Orientations of a Graph
• Unnamed Item
• Unnamed Item

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