Computing the metric dimension of graphs by genetic algorithms

DOI10.1007/s10589-007-9154-5zbMath1191.68469OpenAlexW1968600356MaRDI QIDQ849088

Jozef Kratica, Mirjana Čangalović, Vera V. Kovacevic-Vujcic

Publication date: 24 February 2010

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-007-9154-5

zbMATH Keywords

graph theorymetric dimensionevolutionary approach

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Learning to compute the metric dimension of graphs, An IP-based swapping algorithm for the metric dimension and minimal doubly resolving set problems in hypercubes, Symmetry properties of resolving sets and metric bases in hypercubes, Variable neighborhood search for metric dimension and minimal doubly resolving set problems, Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Resolving the hypercube, On the metric dimension of infinite graphs, An ILP formulation and genetic algorithm for the maximum degree-bounded connected subgraph problem, Computing minimal doubly resolving sets of graphs, Low-dimensional representation of genomic sequences, A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem, Minimal doubly resolving sets of prism graphs

Uses Software

• GLOB
• CPLEX
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• The metric dimension of Cayley digraphs
• Two genetic algorithms for solving the uncapacitated single allocation \(p\)-hub median problem
• Genetic algorithms for solving the discrete ordered median problem
• A tree search algorithm for the crew scheduling problem
• Guidelines for the use of meta-heuristics in combinatorial optimization.
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• Improving graph colouring algorithms and heuristics using a novel representation
• The core concept for the Multidimensional Knapsack problem
• A tabu search algorithm for the quadratic assignment problem
• Obtaining test problems via Internet
• Genetic and hybrid algorithms for graph coloring
• Probabilistic diversification and intensification in local search for vehicle routing
• Many hard examples in exact phase transitions
• Landmarks in graphs
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Connected Resolvability of Graphs
• On Connected Resolving Decompositions in Graphs
• SOLVING THE UNCAPACITATED MULTIPLE ALLOCATION p-HUB CENTER PROBLEM BY GENETIC ALGORITHM
• On the metric dimension of some families of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• On some interconnections between combinatorial optimization and extremal graph theory
• A single period inventory model of a deteriorating item sold from two shops with shortage via genetic algorithm
• Variable neighborhood search: Principles and applications