Authors: Ćirković, Petar 
Đorđević, Predrag
Milićević, Miloš
Davidović, Tatjana 
Affiliations: Computer Science 
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
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

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.