Hardness of metric dimension in graphs of constant treewidth

DOI10.1007/S00453-022-01005-YOpenAlexW3131586115MaRDI QIDQ2093561

Shao-hua Li, Marcin Pilipczuk

Publication date: 27 October 2022

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

NP-hardgraph algorithmsconstant treewidth

Mathematics Subject Classification ID

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

Related Items (1)

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of metric dimension on planar graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Interval graphs and searching
• 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
• Reducibility among Combinatorial Problems
• Metric Dimension of Bounded Tree-length Graphs

This page was built for publication: Hardness of metric dimension in graphs of constant treewidth