Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications

DOI10.1137/21m1409512zbMath1527.05055arXiv2104.07201OpenAlexW3153521189MaRDI QIDQ6071823

Rafael Frongillo, Richard C. Tillquist, Manuel E. Lladser

Publication date: 29 November 2023

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.07201

zbMATH Keywords

graph embedding resolving set metric dimension graph isomorphism multilateration

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

A linear time algorithm for metric dimension of cactus block graphs
Computing the metric dimension of wheel related graphs
On the metric dimension of circulant and Harary graphs
The difference between the metric dimension and the determining number of a graph
Complexity of metric dimension on planar graphs
Metric dimension of some distance-regular graphs
The metric dimension of metric spaces
Metric dimension for random graphs
On the metric dimension of bilinear forms graphs
On the metric dimension of circulant graphs
Approximation complexity of metric dimension problem
The structure and metric dimension of the power graph of a finite group
The metric dimension of geometric spaces
On metric dimension of permutation graphs
The (weighted) metric dimension of graphs: hard and easy cases
Computing the metric dimension of a graph from primary subgraphs
On the metric dimension of imprimitive distance-regular graphs
Resolvability and strong resolvability in the direct product of graphs
Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
On families of convex polytopes with constant metric dimension
On the metric dimension of corona product graphs
Metric dimension and \(R\)-sets of connected graphs
The Erdős-Rényi law in distribution, for coin tossing and sequence matching
Mastermind
Maker-Breaker domination game
Metric dimension and pattern avoidance in graphs
The metric dimension of Cayley digraphs
Computing the metric dimension of graphs by genetic algorithms
Identifying graph automorphisms using determining sets
The effect of vertex or edge deletion on the metric dimension of graphs
Extending the metric dimension to graphs with missing edges
An efficient representation of Benes networks and its applications
On minimum metric dimension of honeycomb networks
On the determining number and the metric dimension of graphs
On the algorithmic complexity of the Mastermind game with black-peg results
Graph isomorphism is in the low hierarchy
On the order of uniprimitive permutation groups
A metric basis characterization of Euclidean spaces
On \(k\)-dimensional graphs and their bases
Resolvability and the upper dimension of graphs
Resolvability in graphs and the metric dimension of a graph
Uniquely identifying the edges of a graph: the edge metric dimension
On the metric dimension of incidence graphs
On the edge dimension of a graph
Rigidity and separation indices of Paley graphs
Conditional resolvability in graphs: a survey
Variable neighborhood search for metric dimension and minimal doubly resolving set problems
Resolving sets for Johnson and Kneser graphs
On the metric dimension of line graphs
On the strong metric dimension of corona product graphs and join graphs
Resolving sets and semi-resolving sets in finite projective planes
The partition dimension of a graph
Metric properties of generalized Sierpiński graphs over stars
Metric dimension parameterized by treewidth
Maker-breaker resolving game
Metric dimension of maximal outerplanar graphs
On vertices contained in all or in no metric basis
Truncated metric dimension for finite graphs
Bounds on metric dimensions of graphs with edge disjoint cycles
Computing a metric basis of a 2-connected bipartite distance-hereditary graph
The connected metric dimension at a vertex of a graph
Alternative parameterizations of \textsc{Metric Dimension}
The metric dimension of \(\mathbb{Z}_n \times \mathbb{Z}_n \times \mathbb{Z}_n\) is \(\lfloor 3n/2 \rfloor \)
Metric dimension of Cayley digraphs of split metacyclic groups
Low-dimensional representation of genomic sequences
Metric dimension of generalized wheels
Computing the metric dimension for chain graphs
On the limiting distribution of the metric dimension for random forests
Extremal graph theory for metric dimension and diameter
Computing the metric dimension of convex polytopes generated by wheel related graphs
A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
The \(k\)-metric dimension
On the metric dimension of Cartesian powers of a graph
Practical graph isomorphism. II.
On the metric dimension, the upper dimension and the resolving number of graphs
Tight approximability results for test set problems in bioinformatics
Smith's theorem and a characterization of the 6-cube as distance-transitive graph
Landmarks in graphs
Levenshtein graphs: resolvability, automorphisms \& determining sets
Metric dimension of dual polar graphs
The directed distance dimension of oriented graphs
The metric dimension of strong product graphs
On the Metric Dimension of Infinite Graphs
On the metric dimension of generalized Petersen graphs
On the Complexity of Metric Dimension
Characterization of n-Vertex Graphs with Metric Dimension n-3
Metric dimension of directed graphs
Metric Dimension Parameterized by Max Leaf Number
The metric dimension of small distance-regular and strongly regular graphs
An Optimal Strategy for Static Black-Peg Mastermind with Two Pegs
The Metric Dimension of Circulant Graphs
Strong metric dimension: A survey
Domination Game and an Imagination Strategy
The Metric Dimension of Regular Bipartite Graphs
Complexity Theory
Base size, metric dimension and other invariants of groups and graphs
Landmarks in torus networks
On the metric dimension of some families of graphs
On the Metric Dimension of Cartesian Products of Graphs
Metric bases in digital geometry
Domination and location in acyclic graphs
On the Complexity of Canonical Labeling of Strongly Regular Graphs
Random Graph Isomorphism
Structure-activity maps for visualizing the graph variables arising in drug design
On a new class of codes for identifying vertices in graphs
The Metric Dimension of Two-Dimensional Extended Meshes
The relationship between node degree and dissipation rate in networks of diffusively coupled oscillators and its significance for pancreatic beta cells
Error Detecting and Error Correcting Codes
On the metric dimension of affine planes, biaffine planes and generalized quadrangles
Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
The metric dimension of circulant graphs and their Cartesian products
Lexicographic metric spaces: Basic properties and the metric dimension
Reducibility among Combinatorial Problems
Finite metric and 𝑘-metric bases on ultrametric spaces
Resolvability of Hamming Graphs
Metric dimension of metric transform and wreath product
On the k-metric dimension of metric spaces
On distances in Sierpiński graphs: Almost-extreme vertices and metric dimension
Metric Dimension of Bounded Tree-length Graphs
Rumors in a Network: Who's the Culprit?
The Metric Dimension of the Total Graph of a Finite Commutative Ring
Mathematical Foundations of Computer Science 2004
Graph isomorphism in quasipolynomial time [extended abstract]
On the metric dimension of Grassmann graphs
On the dimension of a graph
The complexity of theorem-proving procedures
On Metric Generators of Graphs
A Combinatory Detection Problem
On metric dimensions of hypercubes
The metric dimension of the lexicographic product of graphs
Graph-Theoretic Concepts in Computer Science
Computational Complexity
On a combinatorial game
The metric dimension of the lexicographic product of graphs
Metric dimension: from graphs to oriented graphs
On metric dimensions of symmetric graphs obtained by rooted product
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
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
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item

This page was built for publication: Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications