Optimizing Urban Resource Allocation Using Minimum Dominating Sets in Interval Graphs

Efficient resource allocation in urban environments is a critical challenge for modern city planning, particularly in the context of limited budgets and increasing service demands. This paper presents a graph-theoretic approach to optimizing resource allocation by modeling urban zones as interval graphs and identifying Minimum Dominating Sets (MDS) to ensure complete coverage with minimal redundancy. We apply a linear-time MDS algorithm to a case study involving a six-zone urban corridor and demonstrate that full spatial coverage can be achieved using only three zones, effectively halving the number of necessary deployments compared to uniform or heuristic strategies. The results highlight the method’s efficiency, scalability, and potential for integration into real-world planning tools. Discussion includes computational performance, resilience through moderate redundancy, and practical implications for urban infrastructure design. The proposed approach offers a promising solution for data-driven, cost-effective urban resource optimization.