Graph Neural Network for Minimum Dominating Set

Download Now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 459.92 KB