Computing strong metric dimension of some special classes of graphs by genetic algorithms
DOI:
https://doi.org/10.2298/YJOR0802143KKeywords:
strong metric dimension, genetic algorithms, evolutionary approachAbstract
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.References
Beasley, J.E. (1996) Obtaining test problems via Internet. Journal of Global Optimization, 8(4): 429
Beasley, J.E., Cao, B. (1996) A tree search algorithm for the crew scheduling problem. European Journal of Operational Research, 94(3): 517
Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihalak, M., Ram, L.S. (2006) Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12): 2168
Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R. (2007) On the Metric Dimension of Cartesian Products of Graphs. SIAM Journal on Discrete Mathematics, 21(2): 423
Chartr, G., Eroha, L., Johnson, M.A., Oellermann, O.R. (2000) Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3): 99
Chartr, G., Poisson, C., Zhang, P. (2000) Resolvability and the upper dimension of graphs. Computers & Mathematics with Applications, 39(12): 19
Currie, J.D., Oellerman, O.R. (2001) The metric dimension and metric independence of a graph. Journal of Combinatorial Mathematics and Combinatorial Computing, 39, 157-167
Đurić, B., Kratica, J., Tošić, D., Filipović, V. (2008) Solving the maximally balanced connected partition problem in graphs by using genetic algorithm. Computing and Informatics, 27 (2), in press
Filipović, V. (2003) Fine-grained tournament selection operator in genetic algorithms. Computing and Informatics, vol. 22, br. 2, str. 143-161
Filipović, V. (2006) Selection and migration operators and Web services in parallel evolutionary algorithms. Faculty of Mathematics, PhD thesis, in Serbian
Fleurent, C., Ferland, J.A. (1996) Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, 63(3): 437
Harary, F., Melter, R.A. (1976) On the metric dimension of a graph. Ars Combinatoria, 2 191-195
Hernando, C., Mora, M., Pelayo, I.M., i dr. (2005) On the metric dimension of some families of graphs. Electronic Notes in Discrete Mathematics, 22, 129
Hernando, C., Mora, M., Pelayo, I.M., i dr. (2007) Extremal graph theory for metric dimension and diameter. Electronic Notes in Discrete Mathematics, 29: 339
Khuller, S., Raghavachari, B., Rosenfeld, A. (1996) Landmarks in graphs. Discrete Applied Mathematics, 70(3): 217
Kratica, J., Kovačević-Vujčić, V., Čangalović, M. (2008) Computing the metric dimension of graphs by genetic algorithms. Computational Optimization and Applications
Kratica, J., Čangalović, M., Kovačević-Vujčić, V. (2009) Computing minimal doubly resolving sets of graphs. Computers & Operations Research, in press
Ljubić, I., Raidl, G.R. (2003) A memetic algorithm for minimum-cost vertex-biconnectivity augmentation of graphs. Journal of Heuristics, 9(5): 401
Ljubić, I. (2004) Exact and memetic algorithms for two network design problems. Vienna: University of Technology - Institute of Computer Graphics, PhD thesis
Mitchell, M. (1999) An introduction to genetic algorithms. Cambridge, MA, itd: Massachusetts Institute of Technology Press / MIT Press
Oellermann, O., Fehr, M., Gosselin, S. (2006) The metric dimension of Cayley digraphs. Discrete Mathematics, 306(1): 31
Oellermann, O., Peters-Fransen, J. (2006) The metric dimension of Cartesian products of graphs. Utilitas Mathematica, 69 33-41
Oellermann, O., Peters-Fransen, J. (2007) The strong metric dimension of graphs and digraphs. Discrete Applied Mathematics, 155(3): 356
Sebö, A., Tannier, E. (2004) On metric generators of graphs. Mathematics of Operations Research, 29(2): 383
Shanmukha, B., Sooryanarayana, B., Harinath, K.S. (2002) Metric dimension of wheels. Far East Journal of Applied Mathematics, 8, 217-229
Slater, P.J. (1975) Leaves of trees. Congr. Numerantium, 14 549-559
Stanimirovic, Z. (2010) A Genetic Algorithm Approach For The Capacitated Single Allocation P-hub Median Problem. Computing and Informatics, vol. 29, br. 1, str. 117-132
Stanimirović, Z. (2004) Solving some discrete location problems by using genetic algorithms. Belgrade: Faculty of Mathematics, Master's thesis
Stanimirović, Z. (2007) Genetic algorithms for solving some NP-hard hub location problems'. Belgrade: Faculty of Mathematics, Ph.D. thesis
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
