Network-Algorithms

Mathematical algorithms developed in python

1. Minimum Dominating Set (minDominatingSet.py)

Calculates the Minimum Dominating Set in a given Graph

###Sample Output: Vertices in the Graph = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Edges in the Graph = {(2, 7), (1, 2), (6, 9), (10, 4), (8, 2), (7, 1), (10, 7), (6, 8), (5, 6), (9, 3), (4, 5), (8, 10), (2, 3), (5, 1), (3, 4), (9, 7)}

Yellow Vertices = {1, 2, 3, 4, 6, 7, 10}

Minimum Dominating Set (Red coloured) = {8, 9, 5}

2. Minimum Indepedent Dominating Set, Minimum Connected Dominating Set and Domination Number (minIndependentDOM.py)

Calculates the Minimum Independent Dominating Set, Minimum Connected Dominating Set and Domination Number in a given Graph

###Sample Output: Vertices in the Graph = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}

Edges in the Graph = [(1, 2), (2, 3), (3, 4), (4, 5), (2, 5), (2, 6), (6, 7), (7, 8), (2, 9), (2, 10), (2, 11), (2, 12), (7, 13)]

Minimum Independent Dominating set in the graph = {2, 4, 7}

Minimum Connected Dominating set in the graph = {2, 3, 4, 6, 7}

Domination Number of the graph = 5