Complex Networks

106 

Complex Networks: An Algorithmic Perspective

(b)

(a)

Figure 6.5: Execution of MDS Alg1 in two iterations

black, resulting in n −1 steps where coloring of u and v black suffices to form a DS

in two steps. Guha-Khuller algorithms provide improvements to MDS

Alg so that

such cases are handled more efficiently as described in the next sections.

6.3.2 Guha-Khuller First MCDS Algorithm

In the first algorithm proposed by Guha and Khuller called MCDS Alg1, we start

by coloring the highest degree vertex black and all of its neighbors gray as before.

However, we scan all the gray nodes and their white neighbors and check the spans

of gray nodes and the pair con ...