Graph Neural Network for Minimum Dominating Set

Date Added: Oct 2012
Format: PDF

The dominating set concept in graphs has been used in many applications. In large graphs finding the minimum dominating set is difficult. The minimum dominating set problem in graphs seek a set D of minimum number of vertices such that each vertex of the graph is either in D or adjacent to a vertex in D. In a graph on n nodes if there is a single node of degree n-1 then that single node forms a minimum dominating set. In the proposed paper, a designed network called Graph Neural Network (GNN) is used to identify the node of degree N-1 in a graph having a single node of degree N-1 as it forms the minimum dominating set in the graph.