Metric Dimension Parameterized by Max Leaf Number

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.

11 pages, 2 figures; to appear in J. Graph Algorithms & Applications

Cited by in corpus (4)

• Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• Monitoring edge-geodetic sets in graphs
• Algorithms and hardness for Metric Dimension on digraphs