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