Hardness of metric dimension in graphs of constant treewidth
type: Item
instance of: scholarly article
title: Hardness of metric dimension in graphs of constant treewidth
author: Shao-Hua Li
author: Marcin Pilipczuk
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
full work available at URL: https://arxiv.org/abs/2102.09791
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608286
zbMATH Keywords: graph algorithms
zbMATH Keywords: constant treewidth
zbMATH Keywords: NP-hard
MaRDI profile type: Publication
OpenAlex ID: W3131586115
cites work: Metric Dimension of Bounded Tree-length Graphs
cites work: Q5875537
cites work: Complexity of metric dimension on planar graphs
cites work: Metric Dimension Parameterized by Max Leaf Number
cites work: The (weighted) metric dimension of graphs: hard and easy cases
cites work: Computing the metric dimension for chain graphs
cites work: Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
cites work: Q4119237
cites work: Reducibility among Combinatorial Problems
cites work: Landmarks in graphs
cites work: Interval graphs and searching
cites work: Q4075485
DOI: 10.1007/S00453-022-01005-Y
description: scientific article; zbMATH DE number 7608286