Metric dimension parameterized by max leaf number

DOI10.7155/JGAA.00360MaRDI QIDQ2941747zbMATH OpenOpenAlexWikidataFDO

Authors David Eppstein

Publication date 25 August 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1506.01749

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

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.

Recommendations

• On the Complexity of Metric Dimension
• Alternative parameterizations of \textsc{Metric Dimension}
• Computing the metric dimension for chain graphs
• Complexity of metric dimension on planar graphs
• scientific article; zbMATH DE number 7068461

Cited in

(22)

• Computing the \(k\)-metric dimension of graphs
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Metric dimension parameterized by treewidth
• Hardness of metric dimension in graphs of constant treewidth
• Alternative parameterizations of \textsc{Metric Dimension}
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Computing the metric dimension of a graph from primary subgraphs
• Parameterized complexity of geodetic set
• Metric Dimension of Bounded Tree-length Graphs
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
• Parameterized Complexity of Geodetic Set
• Monitoring edge-geodetic sets in graphs
• Distance-based covering problems for graphs of given cyclomatic number
• Source detection on graphs
• Algorithms and hardness for metric dimension on digraphs
• Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover
• Monitoring edge-geodetic sets in graphs
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number
• Enumerating minimal solution sets for metric graph problems
• Modularity clustering parameterized by max leaf number
• Metric dimension and geodetic set parameterized by vertex cover

This page was built for publication: Metric dimension parameterized by max leaf number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941747)