Approximation for the minimum cost doubly resolving set problem

DOI10.1016/J.TCS.2015.03.048MaRDI QIDQ896151zbMATH OpenOpenAlexFDO

Authors Xiaodong Hu, Changjun Wang, Xujin 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

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

Recommendations

• Approximability of the minimum weighted doubly resolving set problem
• Approximating Minimum Cost Source Location Problems with Local Vertex-Connectivity Demands
• Computation of the double metric dimension in convex polytopes
• Approximating minimum cost source location problems with local vertex-connectivity demands
• Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs

Cites work

• scientific article; zbMATH DE number 2068163 (Why is no real title available?)
• Approximation complexity of metric dimension problem
• Approximation hardness of dominating set problems in bounded degree graphs
• Computing minimal doubly resolving sets of graphs
• Design and analysis of approximation algorithms
• Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
• Minimal doubly resolving sets and the strong metric dimension of some convex polytopes
• Minimal doubly resolving sets of prism graphs
• On Metric Generators of Graphs
• On the Complexity of Metric Dimension
• On the Metric Dimension of Cartesian Products of Graphs
• Optimizing over Consecutive 1's and Circular 1's Constraints
• Rumors in a Network: Who's the Culprit?
• The (weighted) metric dimension of graphs: hard and easy cases
• Tight approximability results for test set problems in bioinformatics
• Variable neighborhood search for metric dimension and minimal doubly resolving set problems

Cited in

(12)

• 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
• Budgeted sensor placement for source localization on trees
• Computing edge version of metric and double metric dimensions of kayak paddle graphs
• 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
• Approximability of the minimum weighted doubly resolving set 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)