Metaheuristics for finding threshold graphs with maximum spectral radius
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916304002220032 |
|---|---|
| author | Radanović, Luka Fellague, Abdelkadir Ostojić, Dragutin Stevanović, Dragan Davidović, Tatjana |
| author_facet | Radanović, Luka Fellague, Abdelkadir Ostojić, Dragutin Stevanović, Dragan Davidović, Tatjana |
| contents | We consider the problem of characterizing graphs with the maximum spectral radius among the connected graphs with given numbers of vertices and edges. It is well-known that the candidates for extremal graphs are threshold graphs, but only a few partial theoretical results have been obtained so far. Therefore, we approach to this problem from a novel perspective that involves incomplete enumeration of different threshold graphs with a given characteristic. Our methodology defines the considered problem as an optimization task and utilizes two metaheuristic methods, Variable Neighborhood Search (VNS), which relies on iterative improvements of a single current best solution and Bee Colony Optimization (BCO), a population-based metaheuristic from the Swarm Intelligence (SI) class. We use compact solution representation and several auxiliary data structures that should enable efficient search of the solution space. In addition, we define several types of transformations that preserve the feasibility of the resulting solution. The proposed methods are compared on the graphs with a moderate number of vertices. Preliminary results are in favor of the VNS approach, however, we believe that both methods could be improved. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19209 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Metaheuristics for finding threshold graphs with maximum spectral radius Radanović, Luka Fellague, Abdelkadir Ostojić, Dragutin Stevanović, Dragan Davidović, Tatjana Combinatorics 05C50, 90C35 We consider the problem of characterizing graphs with the maximum spectral radius among the connected graphs with given numbers of vertices and edges. It is well-known that the candidates for extremal graphs are threshold graphs, but only a few partial theoretical results have been obtained so far. Therefore, we approach to this problem from a novel perspective that involves incomplete enumeration of different threshold graphs with a given characteristic. Our methodology defines the considered problem as an optimization task and utilizes two metaheuristic methods, Variable Neighborhood Search (VNS), which relies on iterative improvements of a single current best solution and Bee Colony Optimization (BCO), a population-based metaheuristic from the Swarm Intelligence (SI) class. We use compact solution representation and several auxiliary data structures that should enable efficient search of the solution space. In addition, we define several types of transformations that preserve the feasibility of the resulting solution. The proposed methods are compared on the graphs with a moderate number of vertices. Preliminary results are in favor of the VNS approach, however, we believe that both methods could be improved. |
| title | Metaheuristics for finding threshold graphs with maximum spectral radius |
| topic | Combinatorics 05C50, 90C35 |
| url | https://arxiv.org/abs/2406.19209 |