×

Computing minimal doubly resolving sets of graphs. (English) Zbl 1158.90414

Summary: We consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to \(2^{90}\) nodes, that cannot be directly handled by the computer.

MSC:

90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C., On the metric dimension of Cartesian products of graphs, SIAM Journal on Discrete Mathematics, 21, 2, 423-441 (2007) · Zbl 1139.05314
[2] Slater, P. J., Leaves of trees, Congressus Numerantium, 14, 549-559 (1975)
[3] Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combinatoria, 2, 191-195 (1976) · Zbl 0349.05118
[4] Beerliova, Z.; Eberhard, F.; Erlebach, T.; Hall, A.; Hoffmann, M.; Mihalák, M., Network discovery and verification, IEEE Journal on Selected Areas in Communications, 24, 12, 2168-2181 (2006)
[5] Chartrand, G.; Eroha, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Applied Mathematics, 105, 99-113 (2000) · Zbl 0958.05042
[6] Currie, J. D.; Oellerman, O. R., The metric dimension and metric independence of a graph, Journal of Combinatorial Mathematics and Combinatorial Computing, 39, 157-167 (2001) · Zbl 0986.05040
[7] Fehr, M.; Gosselin, S.; Oellermann, O. R., The metric dimension of Cayley digraphs, Discrete Mathematics, 306, 1, 31-41 (2006) · Zbl 1085.05034
[8] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Cáceres, J.; Puertas, M. L., On the metric dimension of some families of graphs, Electronic Notes in Discrete Mathematics, 22, 129-133 (2005) · Zbl 1182.05050
[9] Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Wood, D. R., Extremal graph theory for metric dimension and diameter, Electronic Notes in Discrete Mathematics, 29, 339-343 (2007) · Zbl 1341.05132
[10] Oellermann, O.; Fehr, M.; Gosselin, S., The metric dimension of Cayley digraphs, Discrete Mathematics, 306, 31-41 (2006) · Zbl 1085.05034
[11] Oellermann, O.; Peters-Fransen, J., The metric dimension of Cartesian products of graphs, Utilitas Mathematica, 69, 33-41 (2006) · Zbl 1109.05041
[12] Shanmukha, B.; Sooryanarayana, B.; Harinath, K. S., Metric dimension of wheels, Far East Journal of Applied Mathematics, 8, 217-229 (2002) · Zbl 1032.05044
[13] Liu K, Abu-Ghazaleh N. Virtual coordinate backtracking for void traversal in geographic routing, 30 May 2006, arXiv:cs.NI/0511059 v2.; Liu K, Abu-Ghazaleh N. Virtual coordinate backtracking for void traversal in geographic routing, 30 May 2006, arXiv:cs.NI/0511059 v2.
[14] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Applied Mathematics, 70, 217-229 (1996) · Zbl 0865.68090
[15] Kratica J, Kovačević-Vujčić V, Č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, Kovačević-Vujčić V, Č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
[16] Chartrand, G.; Poisson, C.; Zhang, P., Resolvability and the upper dimension of graphs, Computers and Mathematics with Applications, 39, 19-28 (2000) · Zbl 0953.05021
[17] Kabatianski, G.; Lebedev, V. S.; Thorpe, J., The Mastermind game and the rigidity of Hamming spaces, (Proceedings of the IEEE international symposium on information theory—ISIT’00 (2000)), 375
[18] Sebö, A.; Tannier, E., On metric generators of graphs, Mathematics & Operations Research, 29, 2, 383-393 (2004) · Zbl 1082.05032
[19] Lindström, B., On a combinatory detection problem, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 9, 195-207 (1964) · Zbl 0154.44005
[20] Filipović V. Selection and migration operators and Web services in parallel evolutionary algorithms. PhD thesis, University of Belgrade, Faculty of Mathematics; 2006 (in Serbian).; Filipović V. Selection and migration operators and Web services in parallel evolutionary algorithms. PhD thesis, University of Belgrade, Faculty of Mathematics; 2006 (in Serbian).
[21] Mitchell, M., An introduction to genetic algorithms (1999), MIT Press: MIT Press Cambridge, MA
[22] 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. Solving some discrete location problems by using genetic algorithms. Master’s thesis, Faculty of Mathematics, University of Belgrade; 2004 (in Serbian).
[23] Stanimirović Z. Genetic algorithms for solving some NP-hard hub location problems. PhD thesis, University of Belgrade, Faculty of Mathematics; 2007 (in Serbian).; Stanimirović Z. Genetic algorithms for solving some NP-hard hub location problems. PhD thesis, University of Belgrade, Faculty of Mathematics; 2007 (in Serbian).
[24] Almeida, M. T.; Schütz, G.; Carvalho, F. D., Cell suppression problem: a genetic-based approach, Computers & Operations Research, 35, 5, 1613-1623 (2008) · Zbl 1211.90042
[25] Caumond, A.; Lacomme, P.; Tchernev, N., A memetic algorithm for the job-shop with time-lags, Computers & Operations Research, 35, 7, 2331-2356 (2008) · Zbl 1177.90147
[26] Drezner, Z., Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem, Computers & Operations Research, 35, 3, 717-736 (2008) · Zbl 1278.90463
[27] Essafi, I.; Mati, Y.; Dauzere-Perés, S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers & Operations Research, 35, 8, 2599-2616 (2008) · Zbl 1177.90155
[28] Mendes, J. J.M.; Goncalves, J. F.; Resende, M. G.C., A random key based genetic algorithm for the resource constrained project scheduling problem, Computers & Operations Research, 36, 1, 92-109 (2009) · Zbl 1163.90500
[29] Pezzella, F.; Morganti, G.; Ciaschetti, G., A genetic algorithm for the flexible job-shop scheduling problem, Computers & Operations Research, 35, 10, 3202-3212 (2008) · Zbl 1162.90014
[30] Filipović, V., Fine-grained tournament selection operator in genetic algorithms, Computing and Informatics, 22, 143-161 (2003) · Zbl 1076.68609
[31] Stanimirović, Z.; Kratica, J.; Dugošija, Dj., Genetic algorithms for solving the discrete ordered median problem, European Journal of Operational Research, 182, 3, 983-1001 (2007) · Zbl 1121.90087
[32] Djurić, B.; Kratica, J.; Tošić, D.; Filipović, V., Solving the maximally balanced connected partition problem in graphs by using genetic algorithm, Computing and Informatics, 27, 3, 341-354 (2008) · Zbl 1324.05189
[33] Kratica, J.; Stanimirović, Z.; Tošić, D.; Filipović, V., Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem, European Journal of Operational Research, 182, 1, 15-28 (2007) · Zbl 1128.90038
[34] Stanimirović Z. A genetic algorithm approach for the capacitated single allocation p-hub median problem. Computing and Informatics 2008;27; in press.; Stanimirović Z. A genetic algorithm approach for the capacitated single allocation p-hub median problem. Computing and Informatics 2008;27; in press.
[35] Kratica, J.; Kovačević-Vujčić, V.; Čangalović, M., Computing strong metric dimension of some special classes of graphs by genetic algorithms, Yugoslav Journal of Operations Research, 18, 2, 143-151 (2008) · Zbl 1199.68546
[36] Xu, K.; Li, W., Many hard examples in exact phase transitions, Theoretical Computer Science, 355, 291-302 (2006), \( \langle\) http://www.nlsde.buaa.edu.cn/∼kexu/benchmarks/pb-benchmarks.htm \(\rangle \) · Zbl 1088.68163
[37] Beasley, J. E., Obtaining test problems via internet, Journal of Global Optimization, 8, 429-433 (1996), \( \langle\) http://www.brunel.ac.uk/depts/ma/research/∼jeb/orlib \(\rangle \) · Zbl 0848.90126
[38] Beasley, J. E.; Cao, B., A tree search algorithm for the crew scheduling problem, European Journal of Operational Research, 94, 517-526 (1996) · Zbl 0947.90577
[39] Fleurent, C.; Ferland, J. A., Genetic and hybrid algorithms for graph coloring, Annals of Operations Research, 63, 437-461 (1996) · Zbl 0851.90095
[40] Erdős, P.; Rényi, A., On two problems of information theory, Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 8, 229-243 (1963) · Zbl 0119.34001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.