There is a step in Bron–Kerbosch algorithm

for each vertex v in a degeneracy ordering of G:

what is "a degeneracy ordering of G"? For example what is vertex in a degeneracy ordering in

this graph

  • 3
    $\begingroup$ This is a site for research-level questions in theoretical computer science. The answer to your question can be found in a link from the wikilink of your post. $\endgroup$ – RJK May 8 '11 at 7:44

See http://en.wikipedia.org/wiki/Degeneracy_(graph_theory)

Essentially, a degeneracy ordering is an ordering on the vertices that you get from repeatedly removing a vertex of minimum degree in the remaining subgraph. The degeneracy of the graph is the smallest number d such that every vertex has at most d neighbors that are later than it in the ordering. Among all possible orderings, the degeneracy orderings minimize this number.

| cite | improve this answer | |

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.