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
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