Optimizing network structures: solving the maximum subgraph problem in grid networks
Rini Dominic, R. Sundara Rajan, T. M. Rajalaxmi, Paul D Manuel · International Journal of Parallel Emergent and Distributed Systems · 2025
This paper explores the Maximum Subgraph Problem (MSP) in square grid networks, aiming to identify induced subgraphs with the maximum number of edges within fixed-size subsets. Using a novel labeling algorithm, we efficiently derive the maximum subgraph of the square grid. Additionally, we present a standard algorithmic approach and provide a Python implementation for MSP resolution, advancing network analysis methodologies. MSP's significance spans various domains, enhancing theoretical understanding and practical applications in network analysis. We also discuss MSP's novelty in genetic interaction networks on a Grid, emphasizing its importance in scientific investigations.