2
$\begingroup$

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale

They describe the Greedy algorithm as follows:

While there is an uncolored vertex v
    choose a color not used by its neighbors and assign it to v

Then they describe a sequential algorithm:

order the vertices in a random way
execute the greedy algorithm

They claim that this algorithm is $O(m+n)$.

Its seems to me that the greedy algorithm is in fact $O(n^2)$. Am I missing something here? Or is the greedy method $O(m)$? ($m$ = edges, $n$ = vertices)

$\endgroup$
4
$\begingroup$

The book probably assumes an adjacency list representation. Each vertex is visited once, so to decide what color it should get, all its neighbors are checked, so each edge is crossed twice (once in each direction).

If you have an adjacency matrix representation, I think it will be $O(n^2)$.

$\endgroup$
  • $\begingroup$ but still, using the edge representation, wouldn't it have to be O(mn)? $\endgroup$ – Jonny5 Apr 20 '12 at 16:21
  • $\begingroup$ @Xaero182 The adjacency list of a vertex only has size equal to the number of its neighbors, so we do not look at ALL the edges for each vertex (that would be $O(mn)$), only edges incident to it, and an edge is incident to two vertices, so it is looked at twice. $\endgroup$ – sxu Apr 20 '12 at 16:27
  • $\begingroup$ Ok, I think I get it: am I correct to conclude that the complexity of the greedy part is O(m+n)? Because there are n assignments and 2m edge lookups? But then, if the graph is connected, we have m >= n-1 and we arrive at O(m). Is this correct? $\endgroup$ – Jonny5 Apr 20 '12 at 16:51
2
$\begingroup$

A careless implementation of the greedy coloring algorithm leads to a $O(n\Delta)$ algorithm. With some care it can easily be implemented in linear time $O(n+m)$. Create an array $used$ with $\Delta + 1$ components and an array $colors$ of length $n$. Initialize $colors$ and $used$ with 0. Now iterate over all nodes. For each node $v$ iterate over the neighbors $w$ of $v$. If $color[w] > 0$ (i.e. $w$ is already colored) set $used[color[w]]=1$. Then sequentially search the minimal k such that $used[k] == 0$. This is the color of $v$, i.e. $color[v] = k$. Then iterate again over the neighbors $w$ of $v$. If $color[w] > 0$ then set $used[color[w]] == 0$. Upon termination $color$ is a valid coloring. The algorithm obviously requires only $O(n+m)$ time. You can find detailed source code in my book on graph algorithms, but that is in German.

$\endgroup$
0
$\begingroup$

there is some extended analysis of the greedy coloring algorithm complexity in this recent paper[1] and some further commentary in [2] that should give an idea about the style of complexity estimation & lower/upper bounds but also the difficulty of establishing precise estimates.

[1] online algorithms for edge coloring by Feder, Motwani, Panigrahy

[2] Can this randomized greedy algorithm be made online? Or being proved impossible?

$\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.