Approximability of the Minimum Weighted Doubly Resolving Set Problem

DOI10.1007/978-3-319-08783-2_31zbMath1332.05132arXiv1404.4676OpenAlexW1609018602MaRDI QIDQ2920473

Changjun Wang, Xu-jin Chen

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsmetric dimensionpolynomial-time solvabilitysource locationdoubly resolving set

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

The equidistant dimension of graphs ⋮ Budgeted sensor placement for source localization on trees ⋮ The \(k\)-metric dimension ⋮ Extending the metric dimension to graphs with missing edges ⋮ A novel approach for detecting multiple rumor sources in networks with partial observations ⋮ Metric dimension of critical Galton-Watson trees and linear preferential attachment trees ⋮ A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem ⋮ Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs ⋮ On doubly resolving sets in graphs ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices ⋮ The power of adaptivity in source identification with time queries on the path

This page was built for publication: Approximability of the Minimum Weighted Doubly Resolving Set Problem