0
$\begingroup$

So I came across this problem that I would like help solving/explaining:

We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All vertexes are marked active at start time. - In every round i, from i=1 and forth, each vertex with utmost 3a active neighbors will be removed from the graph to sub-set H_i and is marked inactive.

A- How many active vertexes will remain after O(log(a)) rounds?

B- What is the tight upper bound (Theta) on the max vertex size of the graph induced by the set of active vertexes after O(log(a)) rounds?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.