2
$\begingroup$

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 1

4
$\begingroup$

The sentence is a little difficult to unpack, but the idea is that:

  1. The vertices in the graph have an ordering (or 'labels').
  2. 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
  3. 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:

https://cs.stackexchange.com/questions/10438/what-is-the-maximum-number-of-shortest-paths-between-any-pair-of-vertices-in-a-c

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.