# Metric Dimension Parameterized by Max Leaf Number

arXiv: https://arxiv.org/abs/1506.01749 · HTML: https://mlsanity.com/paper/1506.01749/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2015.

## Built on by (most cited first, 1 of 1)

- [Solving Multiagent Path Finding on Highly Centralized Networks](https://mlsanity.com/paper/2412.09433/) (2024)

## Abstract (arXiv)

The metric dimension of a graph is the size of the smallest set of vertices whose distances distinguish all pairs of vertices in the graph. We show that this graph invariant may be calculated by an algorithm whose running time is linear in the input graph size, added to a function of the largest possible number of leaves in a spanning tree of the graph.