Approximation for the minimum cost doubly resolving set problem

DOI10.1016/j.tcs.2015.03.048zbMath1332.05131OpenAlexW2058873618MaRDI QIDQ896151

Changjun Wang, Xiao-Dong Hu, Xu-jin Chen

Publication date: 11 December 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.048

zbMATH Keywords

approximation algorithmsmetric dimensionpolynomial-time solvabilitysource locationdoubly resolving set

Mathematics Subject Classification ID

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

Related Items (5)

Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning ⋮ On approximation algorithm for the edge metric dimension problem ⋮ Computation of the double metric dimension in convex polytopes ⋮ Metric-locating-dominating sets of graphs for constructing related subsets of vertices ⋮ Schemes of propagation models and source estimators for rumor source detection in online social networks: A short survey of a decade of research

Cites Work

• Unnamed Item
• Minimal doubly resolving sets and the strong metric dimension of some convex polytopes
• Approximation complexity of metric dimension problem
• Design and analysis of approximation algorithms
• Approximation hardness of dominating set problems in bounded degree graphs
• Computing minimal doubly resolving sets of graphs
• Variable neighborhood search for metric dimension and minimal doubly resolving set problems
• Tight approximability results for test set problems in bioinformatics
• Minimal doubly resolving sets of prism graphs
• On the Complexity of Metric Dimension
• Optimizing over Consecutive 1's and Circular 1's Constraints
• On the Metric Dimension of Cartesian Products of Graphs
• The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
• Rumors in a Network: Who's the Culprit?
• Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
• On Metric Generators of Graphs

This page was built for publication: Approximation for the minimum cost doubly resolving set problem