Back to Search
Start Over
A Population-Based Local Search Algorithm for the Identifying Code Problem.
- Source :
-
Mathematics (2227-7390) . Oct2023, Vol. 11 Issue 20, p4361. 17p. - Publication Year :
- 2023
-
Abstract
- The identifying code problem for a given graph involves finding a minimum subset of vertices such that each vertex of the graph is uniquely specified by its nonempty neighborhood within the identifying code. The combinatorial optimization problem has a wide variety of applications in location and detection schemes. Finding an identifying code of minimum possible size is a difficult task. In fact, it has been proven to be computationally intractable (NP-complete). Therefore, the use of heuristics to provide good approximations in a reasonable amount of time is justified. In this work, we present a new population-based local search algorithm for finding identifying codes of minimum cost. Computational experiments show that the proposed approach was found to be more effective than other state-of-the-art algorithms at generating high-quality solutions in different types of graphs with varying numbers of vertices. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 22277390
- Volume :
- 11
- Issue :
- 20
- Database :
- Academic Search Index
- Journal :
- Mathematics (2227-7390)
- Publication Type :
- Academic Journal
- Accession number :
- 173316888
- Full Text :
- https://doi.org/10.3390/math11204361