Skip to main content

Advertisement

Log in

Computing the metric dimension of graphs by genetic algorithms

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 1: Basic Algorithms and Operators. Institute of Physics Publishing, Bristol (2000)

    MATH  Google Scholar 

  2. Bäck, T., Fogel, D.B., Michalewicz, Z.: Evolutionary Computation 2: Advanced Algorithms and Operators. Institute of Physics Publishing, Bristol (2000)

    MATH  Google Scholar 

  3. Beasley, J.E.: Obtaining test problems via internet. J. Glob. Optim. 8, 429–433 (1996). http://www.brunel.ac.uk/depts/ma/research/jeb/orlib

    Article  MATH  Google Scholar 

  4. Beasley, J.E., Cao, B.: A tree search algorithm for the crew scheduling problem. Eur. J. Oper. Res. 94, 517–526 (1996)

    Article  MATH  Google Scholar 

  5. Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C.: On the metric dimension of some families of graphs. In: Proc. 7th Internacional Colloquium on Graph Theory—ICGT’05, Hyères, France (2005)

  6. Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of graph products. In: Proc. 20th British Combinatorial Conference, Durham, England (2005)

  7. Cáceres, J., Hernando, C., Mora, M., Pelayo, I.M., Puertas, M.L., Seara, C., Wood, D.R.: On the metric dimension of Cartesian products of graphs. SIAM J. Discrete Math. 21(2), 423–441 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chappell, G.G., Gimbel, J., Hartman, C.: Bounds on the metric and partition dimensions of a graph. Manuscript (2003)

  9. Chartrand, G., Eroha, L., Johnson, M.A., Oellermann, O.R.: Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math. 105, 99–113 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  10. Chartrand, G., Poisson, C., Zhang, P.: Resolvability and the upper dimension of graphs. Comput. Math. Appl. 39, 19–28 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Currie, J.D., Oellerman, O.R.: The metric dimension and metric independence of a graph. J. Comb. Math. Comb. Comput. 39, 157–167 (2001)

    MATH  Google Scholar 

  12. Cvetković, D., Hansen, P., Kovačević-Vujčić, V.: On some interconnections between combinatorial optimization and extremal graph theory. Yugosl. J. Oper. Res. 14(2), 147–154 (2004)

    Article  MathSciNet  Google Scholar 

  13. Dorigo, M., Stützle, T.: Ant Colony Optimization. MIT Press, Cambridge (2004)

    MATH  Google Scholar 

  14. Fehr, M., Gosselin, S., Oellermann, O.R.: The metric dimension of Cayley digraphs. Discrete Math. 306(1), 31–41 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  15. Filipović, V.: Fine-grained tournament selection operator in genetic algorithms. Comput. Inform. 22, 143–161 (2003)

    MathSciNet  MATH  Google Scholar 

  16. Filipović, V.: Selection and migration operators and Web services in parallel evolutionary algorithms. Ph.D. thesis, Faculty of Mathematics, University of Belgrade (2006) (in Serbian)

  17. Filipović, V., Kratica, J., Tošić, D., Ljubić, I.: Fine grained tournament selection for the simple plant location problem. In: Proceedings of the 5th Online World Conference on Soft Computing Methods in Industrial Applications—WSC5, pp. 152–158 (2000)

  18. Fleurent, C., Ferland, J.A.: Genetic and hybrid algorithms for graph coloring. Ann. Oper. Res. 63, 437–461 (1996)

    Article  MATH  Google Scholar 

  19. Glover, F., Laguna, F.: Tabu Search. Kluwer Academic, Norwell (1997)

    MATH  Google Scholar 

  20. Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. Eur. J. Oper. Res. 130(3), 449–467 (2001)

    Article  MATH  Google Scholar 

  21. Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976)

    MathSciNet  Google Scholar 

  22. Hertz, A., Widmer, M.: Guidelines for the use of meta-heuristics in combinatorial optimization. Eur. J. Oper. Res. 151, 247–252 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  23. Hernando, C., Mora, M., Pelayo, I.M., Seara, C., Cáceres, J., Puertas, M.L.: On the metric dimension of some families of graphs. Electron. Notes Discrete Math. 22, 129–133 (2005)

    Article  Google Scholar 

  24. Juhos, I., van Hemert, J.I.: Improving graph colouring algorithms and heuristics using a novel representation. In: Lecture Notes in Computer Science, vol. 3906, pp. 123–134. Springer, Berlin (2006)

  25. Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kaufmann, San Francisco (2001)

    Google Scholar 

  26. Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Appl. Math. 70, 217–229 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983). http://citeseer.ist.psu.edu/kirkpatrick83optimization.html

    Article  MathSciNet  Google Scholar 

  28. Kovačević-Vujčić, V., Mladenović, N., Čangalović, M., Dražić, M.: Continuous variable neighborhood search: comparison with exact methods. Yugosl. J. Oper. Res. (accepted for publication)

  29. Kratica, J.: Improving performances of the genetic algorithm by caching. Comput. Artif. Intell. 18, 271–283 (1999)

    MATH  Google Scholar 

  30. Kratica, J.: Parallelization of genetic algorithms for solving some NP-complete problems. Ph.D. thesis, Faculty of Mathematics, University of Belgrade (2000) (in Serbian)

  31. Kratica, J., Stanimirović, Z.: Solving the uncapacitated multiple allocation p-hub center problem by genetic algorithm. Asia-Pacific J. Oper. Res. 24(4), 425–438 (2006)

    Article  Google Scholar 

  32. Kratica, J., Stanimirović, Z., Tošić, D., Filipović, V.: Genetic algorithms for solving uncapacitated multiple allocation hub median problem. Comput. Inform. 24, 415–426 (2005)

    MATH  Google Scholar 

  33. Kratica, J., Stanimirović, Z., Tošić, D., Filipović, V.: Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem. Eur. J. Oper. Res. 182(1), 15–28 (2007)

    Article  MATH  Google Scholar 

  34. Ljubić, I.: Exact and memetic algorithms for two network design problems. Ph.D. thesis, Institute of Computer Graphics, Vienna University of Technology (2004)

  35. Ljubić, I., Raidl, G.R.: A memetic algorithm for minimum-cost vertex-biconnectivity augmentation of graphs. J. Heuristics 9, 401–427 (2003)

    Article  Google Scholar 

  36. Ljubić, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Program. Series B 105(2–3), 427–449 (2006)

    Article  MATH  Google Scholar 

  37. Merz, P.: Advanced fitness landscape analysis and the performance of memetic algorithms. Evol. Comput. 12(3), 303–325 (2004)

    Article  MathSciNet  Google Scholar 

  38. Misevicius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30(1), 95–111 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  39. Mladenović, N., Dražić, M., Kovačević-Vujčić, V., Čangalović, M.: General variable neighborhood search for the continuous optimization. Eur. J. Oper. Res. (2007). doi:10.1016/j.ejor.2006.12.064

    Google Scholar 

  40. Mondel, S.K., Dey, J.K., Maiti, M.: A single period inventory model of a deteriorating item sold from two shops with shortage via genetic algorithm. Yugosl. J. Oper. Res. 17(1), 75–94 (2007)

    Article  MathSciNet  Google Scholar 

  41. Moscato, P.: Memetic algorithms. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization, pp. 157–167. Oxford University Press, Oxford (2002)

    Google Scholar 

  42. Peters-Fransen, J., Oellermann, O.: The metric dimension of Cartesian products of graphs. Util. Math. 69, 33–41 (2006)

    MathSciNet  MATH  Google Scholar 

  43. Puchinger, J., Raidl, G.R., Pferschy, U.: The core concept for the multidimensional knapsack problem. In: Lecture Notes in Computer Science, vol. 3906, pp. 195–208. Springer, Berlin (2006)

  44. Raidl, G.R., Gottlieb, J.: Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: a case study for the multidimensional knapsack problem. Evol. Comput. 13(4), 441–475 (2005)

    Article  Google Scholar 

  45. Rochat, Y., Taillard, E.D.: Probabilistic diversification and intensification in local search for vehicle routing. J. Heuristics 1, 147–167 (1995)

    Article  MATH  Google Scholar 

  46. Saenpholphat, V., Zhang, P.: Connected resolvability of graphs. Czechoslov. Math. J. 53(128), 827–840 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  47. Saenpholphat, V., Zhang, P.: On connected resolving decompositions in graphs. Czechoslov. Math. J. 54(129), 681–696 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  48. Shanmukha, B., Sooryanarayana, B., Harinath, K.S.: Metric dimension of wheels. Far East J. Appl. Math. 8, 217–229 (2002)

    MathSciNet  MATH  Google Scholar 

  49. Stanimirović, Z.: Solving some discrete location problems by using genetic algorithms. Master’s thesis, Faculty of Mathematics, University of Belgrade (2004) (in Serbian)

  50. Stanimirović, Z.: An efficient genetic algorithm for the uncapacitated multiple allocation p-hub median problem. Control Cybern. (submitted)

  51. Stanimirović, Z., Kratica, J., Dugošija, Dj.: Genetic algorithms for solving the discrete ordered median problem. Eur. J. Oper. Res. 182(3), 983–1001 (2007)

    Article  MATH  Google Scholar 

  52. Xu, K., Li, W.: Many hard examples in exact phase transitions. Theor. Comp. Sci. 355, 291–302 (2006). http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/pb-benchmarks.htm

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Jozef Kratica.

Additional information

This research was partially supported by Serbian Ministry of Science under the grant No. 144015G.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kratica, J., Kovačević-Vujčić, V. & Čangalović, M. Computing the metric dimension of graphs by genetic algorithms. Comput Optim Appl 44, 343–361 (2009). https://doi.org/10.1007/s10589-007-9154-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-007-9154-5

Keywords

Navigation