A Malatya Centrality-based algorithm for optimal solutions to maximum independent set and minimum vertex cover problems in lattice graphs
Аннотация
A lattice graph constitutes a fundamental graph type utilized across various domains and for addressing distinct challenges. The literature acknowledges a plethora of lattice graphs, each characterized by unique structures and attributes. Among the problems defined on lattice graphs are the Maximum Independent Set Problem (MISP) and the Minimum Vertex-Cover Problem (MVCP). MISP entails identifying the largest set of vertices in a graph that are not adjacent via edges. Conversely, MVCP involves determining the smallest set of vertices necessary to encompass all edges between nodes. Numerous methodologies have been suggested to resolve these issues within the context of lattice graphs. This research introduces an algorithm to address both MISP and MVCP on lattice graphs, leveraging the Malatya centrality algorithm. The algorithm calculates the centrality values of nodes within a lattice graph based on their degrees. Initially, it identifies the optimal solution set for MISP by employing the Malatya centrality values of the nodes. Subsequently, it ascertains the optimal solution set for MVCP based on the solution derived for MISP. The efficacy of the proposed algorithm was verified through its application to sample lattice graphs of varying sizes and configurations. It offers an efficient and robust solution in polynomial time across different lattice graph categories. Mathematical analysis and empirical studies on prevalent lattice graphs in the literature affirm that the algorithm yields optimal and effective resolutions for MISP and MVCP. Moreover, it generates solutions that are not contingent on constraints such as the number of iterations or initial conditions, and it produces effective outcomes in scenarios where integer linear programming methods fall short.