On approximation algorithm for the edge metric dimension problem

DOI10.1016/j.tcs.2020.05.005zbMath1486.68255OpenAlexW3026730287MaRDI QIDQ2220845

Yanyan Li

Publication date: 25 January 2021

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

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

zbMATH Keywords

greedy algorithmapproximation algorithmsedge metric dimensionsubmodular optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Distance in graphs (05C12) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation complexity of metric dimension problem
• Approximation for the minimum cost doubly resolving set problem
• Computing minimal doubly resolving sets of graphs
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• Uniquely identifying the edges of a graph: the edge metric dimension
• On graphs with the maximum edge metric dimension
• On the edge dimension of a graph
• Tight approximability results for test set problems in bioinformatics
• Landmarks in graphs
• On the Metric Dimension of Infinite Graphs
• The Metric Dimension of Regular Bipartite Graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design

This page was built for publication: On approximation algorithm for the edge metric dimension problem