An Algorithm

1. Partition the vertices into two sets. Put half the vertices in one set and half in another.(extra in first set if number of vertices is odd)

2. ChosenSet = Set1

3. Repeat

A. Find a vertex v in ChosenSet that is adjacent to more vertices in the other set than in ChosenSet

B. If such a v exists

Move v to the other set.

ChosenSet = the other set

Until no such v is found.

4. Make ChosenSet the majority dominating set.

Previous slide

Next slide

Back to first slide

View graphic version