Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00360
Metric Dimension Parameterized by Max Leaf Number
David Eppstein
Vol. 19, no. 1, pp. 313-323, 2015. Regular paper.
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.
Submitted: June 2014.
Reviewed: January 2015.
Revised: April 2015.
Accepted: June 2015.
Final: June 2015.
Published: June 2015.
Communicated by Giuseppe Di Battista
article (PDF)
BibTeX