Metric dimension parameterized by treewidth

DOI10.1007/s00453-021-00808-9OpenAlexW2996877459MaRDI QIDQ2041987

Nidhi Purohit, Édouard Bonnet

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

treewidthmetric dimensionparameterized hardness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (5)

Parameterized Complexity of Geodetic Set ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ 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 ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for metric dimension of cactus block graphs
• Complexity of metric dimension on planar graphs
• Fundamentals of parameterized complexity
• The (weighted) metric dimension of graphs: hard and easy cases
• On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
• Interval graphs and searching
• Resolvability in graphs and the metric dimension of a graph
• Which problems have strongly exponential complexity?
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Computing the metric dimension for chain graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Landmarks in graphs
• Metric Dimension Parameterized by Max Leaf Number
• Metric Dimension of Bounded Tree-length Graphs
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Metric dimension parameterized by treewidth