Computing strong metric dimension of some special classes of graphs by genetic algorithms
In this paper we consider the NP-hard problem of determining the strong metric dimension of graphs. The problem is solved by a genetic algorithm that uses binary encoding and standard genetic operators adapted to the problem. This represents the first attempt to solve this problem heuristically. We...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Belgrade
2008-01-01
|
| Series: | Yugoslav Journal of Operations Research |
| Subjects: | |
| Online Access: | http://www.doiserbia.nb.rs/img/doi/0354-0243/2008/0354-02430802143K.pdf |
| Summary: | In this paper we consider the NP-hard problem of determining the strong metric dimension of graphs. The problem is solved by a genetic algorithm that uses binary encoding and standard genetic operators adapted to the problem. This represents the first attempt to solve this problem heuristically. We report experimental results for the two special classes of ORLIB test instances: crew scheduling and graph coloring. |
|---|---|
| ISSN: | 0354-0243 1820-743X |