Approximation for the minimum cost doubly resolving set problem
DOI10.1016/J.TCS.2015.03.048zbMATH Open1332.05131OpenAlexW2058873618MaRDI QIDQ896151FDOQ896151
Xujin Chen, Changjun Wang, Xiaodong Hu
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
approximation algorithmsmetric dimensionpolynomial-time solvabilitysource locationdoubly resolving set
Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25) Distance in graphs (05C12)
Cites Work
- On the Metric Dimension of Cartesian Products of Graphs
- Minimal doubly resolving sets and the strong metric dimension of some convex polytopes
- Variable neighborhood search for metric dimension and minimal doubly resolving set problems
- On the Complexity of Metric Dimension
- Title not available (Why is that?)
- Approximation complexity of metric dimension problem
- On Metric Generators of Graphs
- Rumors in a Network: Who's the Culprit?
- Approximation hardness of dominating set problems in bounded degree graphs
- Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
- Design and analysis of approximation algorithms
- Computing minimal doubly resolving sets of graphs
- Tight approximability results for test set problems in bioinformatics
- Optimizing over Consecutive 1's and Circular 1's Constraints
- Minimal doubly resolving sets of prism graphs
- The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
Cited In (9)
- The doubly metric dimensions of cactus graphs and block graphs
- Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning
- Metric-locating-dominating sets of graphs for constructing related subsets of vertices
- Computation of the double metric dimension in convex polytopes
- Budget-constrained profit maximization without non-negative objective assumption in social networks
- 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
- Schemes of propagation models and source estimators for rumor source detection in online social networks: A short survey of a decade of research
- On approximation algorithm for the edge metric dimension problem
This page was built for publication: Approximation for the minimum cost doubly resolving set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896151)
