A Population-Based Local Search Algorithm for the Identifying Code Problem

Alejandro Lara-Caballero () and Diego González-Moreno
Additional contact information
Alejandro Lara-Caballero: Department of Applied Mathematics and Systems, Universidad Autónoma Metropolitana, Cuajimalpa, Mexico City 05348, Mexico
Diego González-Moreno: Department of Applied Mathematics and Systems, Universidad Autónoma Metropolitana, Cuajimalpa, Mexico City 05348, Mexico

Mathematics, 2023, vol. 11, issue 20, 1-17

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.

Keywords: identifying code; combinatorial optimization; population-based search; local search; configuration checking (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/20/4361/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/20/4361/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:20:p:4361-:d:1263859

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().