
274
Complex Networks: An Algorithmic Perspective
two unconnected neighbors. This initial step may result in many nodes entering the
CDS than necessary. The algorithm then applies two pruning rules to exclude some
of these nodes from the CDS. In the first rule, a node checks whether a neighbor
CDS node with a higher identifier covers its entire closed neighbor set and if there
is such a node, it exits the CDS. The second rule forces any node which has an open
neighborhood set covered by the union of the open neighborhoods of its two CDS
neighbors which both have higher identifers than itself to exit the CDS. Assuming
a node u in the CDS has color black ...