The answer to this question could be trivial !
Definition:
According to the wikipedia page:
A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex $v$, $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique.
I'm not sure if I understand completely the definition .
Question?
Could somebody explain a little bit the definition, or give some example to illustrate the idea ? ( I have not understand the following sentence "that occur after $v$ in the order")
Any idea will be useful!
$\endgroup$1 Answer
$\begingroup$The sentence is a little difficult to unpack, but the idea is that:
- The vertices in the graph have an ordering (or 'labels').
- For each vertex ($v_i$), take the set (S) consisting of {$v_i$} $\cup N_j(v)$ where $Nj$ is the neighbours of v with position in the ordering > i
- S is a clique
There is an algorithm for creating such an ordering called the maximum cardinality search, which is nice and simple. I found it here but I'm sure it's described in various places.
There are also a couple of examples in this question:
$\endgroup$
