Computing the \(k\)-metric dimension of graphs

DOI10.1016/j.amc.2016.12.005zbMath1411.05077OpenAlexW2561539344WikidataQ57974176 ScholiaQ57974176MaRDI QIDQ1735142

Alejandro Estrada-Moreno, Ismael González Yero, Juan Alberto Rodríguez-Velázquez

Publication date: 28 March 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2016.12.005

zbMATH Keywords

graph algorithmsNP-hard problemmetric dimensionNP-complete problem\(k\)-metric dimension\(k\)-metric dimensional graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the 2-metric resolvability of graphs, Edge metric dimension and mixed metric dimension of planar graph \(Q_n\), Resolving sets tolerant to failures in three-dimensional grids, On 2-partition dimension of rotationally-symmetric graphs, A note on the complexity of \(k\)\textsc{-metric dimension}, Error-correcting codes from \(k\)-resolving sets, A note on \(k\)-metric dimensional graphs, The metric dimension of some generalized Petersen graphs, Mixed metric dimension of graphs, Relationships between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs, Some binary products and integer linear programming for \(k\)-metric dimension of graphs, The \(k\)-metric dimension of corona product graphs, On the \(k\)-partition dimension of graphs, Metric dimension of maximal outerplanar graphs, On the k-metric dimension of metric spaces, Finite metric and 𝑘-metric bases on ultrametric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(k\)-metric dimension of the lexicographic product of graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• On the metric dimension of corona product graphs
• The \(k\)-metric dimension of corona product graphs
• Resolvability in graphs and the metric dimension of a graph
• Error-correcting codes from \(k\)-resolving sets
• The weighted 2-metric dimension of trees in the non-landmarks model
• On the strong metric dimension of corona product graphs and join graphs
• Computing the metric dimension for chain graphs
• Landmarks in graphs
• On the Complexity of Metric Dimension
• Metric Dimension Parameterized by Max Leaf Number
• On the Metric Dimension of Cartesian Products of Graphs
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design
• Resolving domination in graphs
• The independent resolving number of a graph
• On the metric dimension of Grassmann graphs
• On Metric Generators of Graphs
• A Theorem on Boolean Matrices