Study of the Use of the Dominating Set Concept for Router Placement in Campus Networks

Abstract

The development of digital learning in higher education requires the availability of stable and equitable internet network infrastructure. However, the placement of routers on campus is generally still done conventionally without a systematic analytical approach, which has the potential to cause coverage and cost inefficiencies. This study fills this gap by applying graph theory, specifically the concept of dominance sets, to model and optimize router placement in campus buildings. The purpose of this study is to determine the minimum number of routers capable of optimally covering all rooms in support of digital learning at a private university in East Java. This study uses a descriptive quantitative design with a case study approach. The research objects include 27 rooms in a three-story campus building, which are modeled as an undirected graph, where nodes represent rooms and edges indicate physical connections between rooms. Data collection was carried out through direct observation, building layout documentation, and identification of the locations of installed routers. Data analysis was performed using a greedy algorithm to determine the minimal domination set and graph domination number. The results showed that the graph domination number was 10, meaning that only 10 routers were needed to efficiently cover all 27 rooms, compared to the initial condition that used 18 routers. This finding confirms that the application of the dominance set concept can optimize router placement and reduce device requirements without reducing network coverage. The implications of this study indicate that graph theory-based network modeling can be used as a decision-making tool in the design of efficient and sustainable campus internet infrastructure to support digital learning.