A linear time algorithm for metric dimension of cactus block graphs

DOI10.1016/j.tcs.2016.03.024zbMath1339.05388OpenAlexW2305884158WikidataQ56551564 ScholiaQ56551564MaRDI QIDQ278723

Alina Elterman, Stefan Hoffmann, Egon Wanke

Publication date: 2 May 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.03.024

zbMATH Keywords

linear time algorithmresolving setmetric dimensioncactus block graphs

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

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 ⋮ On metric dimensions of symmetric graphs obtained by rooted product ⋮ Nonlocal metric dimension of graphs ⋮ On the status sequences of trees ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Metric dimension parameterized by treewidth ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation complexity of metric dimension problem
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• Landmarks in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On the Complexity of Metric Dimension
• The Metric Dimension of Regular Bipartite Graphs
• On the metric dimension of some families of graphs
• Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite
• Metric bases in digital geometry
• On Metric Generators of Graphs

This page was built for publication: A linear time algorithm for metric dimension of cactus block graphs