咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Hardness of Metric Dimension i... 收藏

Hardness of Metric Dimension in Graphs of Constant Treewidth

作     者:Li, Shaohua Pilipczuk, Marcin 

作者机构:Univ Warsaw Inst Informat Warsaw Poland 

出 版 物:《ALGORITHMICA》 (算法)

年 卷 期:2022年第84卷第11期

页      面:3110-3155页

核心收录:

学科分类:08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

基  金:European Research Council (ERC) under the European Union 

主  题:Graph algorithms constant treewidth NP-hard 

摘      要:The METRIC DIMENSION problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph G. Here, a set S subset of V (G) is resolving if no two distinct vertices of G have the same distance vector to S. The complexity of METRIC DIMENSION in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that METRIC DIMENSION is NP-hard in graphs of treewidth 24.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分