2015/01/01 by David Eppstein · 1 citation
Business, Management and Accounting · Computer Science · Mathematics · #Dimension (graph theory) #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Invariant (physics) #Metric (unit) #Metric dimension #Parameterized complexity #Spanning tree #Varied Academic Research Topics #cs.DS
paper · pdf · doi:10.7155/jgaa.00360
published as J. Graph Algorithms & Applications 19 (1): 313-323, 2015 · 11 pages, 2 figures; to appear in J. Graph Algorithms & Applications
openalex publication_date 2015/01/01 · arxiv created 2015/06/04 · arxiv updated 2015/06/11 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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.