Questions tagged [acyclic-orientations]

An acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

Filter by
Sorted by
Tagged with
5 votes
3 answers
962 views

Acyclic orientations of complete graphs in terms of Stirling numbers?

It is well-known that the number of acyclic orientations of $K_n$ is $n!$. Does anybody know of a combinatorial argument for this fact which uses the identity: $$n!=\sum_{k=1}^ns(n,k),$$ where the $...
1 vote
0 answers
44 views

What is the number of iterations needed for the message passing algorithm to converge when applied to an acyclic factor graph?

I understand that the message passing algorithm (Belief Propagation algorithm), when applied to a factor graph consists in an exchange in messages between the factor nodes and the variable nodes, ...
5 votes
1 answer
161 views

When can we make a digraph acyclic by fliping groups of arcs?

We have a digraph D=(V,A) and its arc set A is partitioned into classes. We can flip the classes, which means changing the direction of all the arcs in the class. Is there any result on when can we ...