On optimal approximability results for computing the strong metric dimension
From MaRDI portal
Publication:512531
DOI10.1016/j.dam.2016.12.021zbMath1357.05030arXiv1408.1390OpenAlexW2134851251MaRDI QIDQ512531
Nasim Mobasheri, Bhaskar Das Gupta
Publication date: 27 February 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.1390
parameterized complexityexponential time hypothesisunique games conjecturestrong metric dimensionapproximabilityminimum node cover
Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Strong resolving graphs: the realization and the characterization problems ⋮ On graphs of order \(n\) with metric dimension \(n-4\) ⋮ On the geodesic identification of vertices in convex plane graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the strong metric dimension of Cartesian and direct products of graphs
- Approximation complexity of metric dimension problem
- Exact exponential algorithms.
- Improved upper bounds for vertex cover
- On the hardness of approximating minimum vertex cover
- The strong metric dimension of graphs and digraphs
- Which problems have strongly exponential complexity?
- On strong metric dimension of graphs and their complements
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Tight approximability results for test set problems in bioinformatics
- Landmarks in graphs
- On Khot’s unique games conjecture
- A measure & conquer approach for the analysis of exact algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the power of unique 2-prover 1-round games
- Reducibility among Combinatorial Problems
- Parameterized Algorithms
- The complexity of theorem-proving procedures
- On Metric Generators of Graphs
- On the complexity of \(k\)-SAT
