Computing the k-metric dimension of graphs

DOI10.1016/J.AMC.2016.12.005MaRDI QIDQ1735142zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Alejandro Estrada-Moreno, Ismael G. Yero, Juan A. 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 algorithmsmetric dimension\(k\)-metric dimensionNP-complete problemNP-hard problem\(k\)-metric dimensional graph

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Metric Dimension
• Computing the metric dimension of a graph from primary subgraphs
• A note on \(k\)-metric dimensional graphs
• k-metric resolvability in graphs
• Complexity of metric dimension on planar graphs

Cites work

• scientific article; zbMATH DE number 3150488 (Why is no real title available?)
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Theorem on Boolean Matrices
• Computing the metric dimension for chain graphs
• Error-correcting codes from \(k\)-resolving sets
• Landmarks in graphs
• Metric bases in digital geometry
• Metric dimension parameterized by max leaf number
• On Metric Generators of Graphs
• On the Complexity of Metric Dimension
• On the Metric Dimension of Cartesian Products of Graphs
• On the metric dimension of Grassmann graphs
• On the metric dimension of corona product graphs
• On the strong metric dimension of corona product graphs and join graphs
• Resolvability in graphs and the metric dimension of a graph
• Resolving domination in graphs
• Structure-activity maps for visualizing the graph variables arising in drug design
• The (weighted) metric dimension of graphs: hard and easy cases
• The \(k\)-metric dimension of corona product graphs
• The \(k\)-metric dimension of the lexicographic product of graphs
• The independent resolving number of a graph
• The local metric dimension of a graph
• The weighted 2-metric dimension of trees in the non-landmarks model

Cited in

(33)

• Computing a metric basis of a 2-connected bipartite distance-hereditary graph
• Computing a metric basis of a bipartite distance-hereditary graph
• Mixed metric dimension of graphs
• A note on the complexity of \(k\)\textsc{-metric dimension}
• Computing hypergraph width measures exactly
• Computing the metric dimension of kayak paddles graph and cycles with chord
• Computing the metric dimension of graphs by genetic algorithms
• \(k\)-metric resolvability in graphs
• The \(k\)-metric dimension
• Metric dimension of maximal outerplanar graphs
• The metric dimension of some generalized Petersen graphs
• A note on \(k\)-metric dimensional graphs
• On the chromatic dimension of a graph
• The \(k\)-metric dimension of corona product graphs
• Error-correcting codes from \(k\)-resolving sets
• On the k-metric dimension of metric spaces
• Metric dimension and some related parameters of different classes of benzenoid system
• On Metric Generators of Graphs
• Some binary products and integer linear programming for \(k\)-metric dimension of graphs
• On 2-partition dimension of rotationally-symmetric graphs
• Complexity of metric dimension on planar graphs
• Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components
• The expected size of some graphs in computational geometry
• On the 2-metric resolvability of graphs
• Finite metric and \(k\)-metric bases on ultrametric spaces
• Computing the metric dimension of a graph from primary subgraphs
• Relationships between the 2-metric dimension and the 2-adjacency dimension in the lexicographic product of graphs
• Computing the metric dimension of gear graphs
• On the \(k\)-partition dimension of graphs
• Metric dimension of directed graphs
• Edge metric dimension and mixed metric dimension of planar graph \(Q_n\)
• Computing the metric dimension for chain graphs
• Resolving sets tolerant to failures in three-dimensional grids

This page was built for publication: Computing the \(k\)-metric dimension of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1735142)