Metric Dimension Parameterized by Max Leaf Number

Authors

  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00360

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2015-01-01

How to Cite

Eppstein, D. (2015). Metric Dimension Parameterized by Max Leaf Number. Journal of Graph Algorithms and Applications, 19(1), 313–323. https://doi.org/10.7155/jgaa.00360

Issue

Section

Articles

Categories