Mathematical Institute of the Serbian Academy of Sciences and Arts
|Title:||Metaheuristic Approach to Spectral Reconstruction of Graphs||Series/Report no.:||Lecture Notes in Computer Science||Volume:||13367||First page:||79||Last page:||93||Conference:||International Conference on Mathematical Optimization Theory and Operations Research MOTOR 2022: Mathematical Optimization Theory and Operations Research||Issue Date:||25-Jun-2022||Rank:||M33||ISBN:||978-3-031-09606-8||DOI:||10.1007/978-3-031-09607-5_6||Abstract:||
Characterization of a graph by its spectrum is a very attractive research problem that has numerous applications. It is shown that the graph is not necessarily uniquely determined by its spectrum in the most general case, i.e., there could be several non-isomorphic graphs corresponding to the same spectrum. All such graphs are called cospectral. However, in most of the cases, it is important to find at least one graph whose spectrum is equal to a given constant vector. This process is called Spectral Reconstruction of Graph (SRG) and it is known as one of the most difficult optimization problems. We address the SRG problem by the metaheuristic methods, more precisely, by Basic Variable Neighborhood Search (BVNS) and improvement-based Bee Colony Optimization (BCOi) methods. The resulting heuristics are called SRG-BVNS and SRG-BCOi, respectively. Both methods are implemented in such a way to take into account the graph properties defined by its spectrum. We compare the performance of the proposed methods with each other and with the results obtained by other approaches from the relevant literature on the reconstruction of some well-known graphs.
|Keywords:||Cospectral graphs | Metaheuristics | Spectral distance | Spectral graph theory||Publisher:||Springer Link||Project:||Advanced artificial intelligence techniques for analysis and design of system components based on trustworthy BlockChain technology - AI4TrustBC|
Show full item record
checked on Mar 23, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.