Complexity of metric dimension on planar graphs
DOI10.1016/J.JCSS.2016.06.006zbMATH Open1350.68119OpenAlexW2460825048MaRDI QIDQ314819FDOQ314819
Authors: J. Díaz, Olli Pottonen, Erik Jan van Leeuwen, Maria Serna 
Publication date: 16 September 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.06.006
Recommendations
- On the Complexity of Metric Dimension
- On the metric dimension of a graph
- Metric dimension of maximal outerplanar graphs
- On metric dimension of graphs and their complements
- On the complexity of embedding planar graphs to minimize certain distance measures
- Computing the \(k\)-metric dimension of graphs
- The metric dimension and girth of graphs
- scientific article; zbMATH DE number 6739348
- Asymptotic dimension of planes and planar graphs
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Cites Work
- Title not available (Why is that?)
- Resolvability in graphs and the metric dimension of a graph
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- Base size, metric dimension and other invariants of groups and graphs
- On the Metric Dimension of Cartesian Products of Graphs
- Efficient Planarity Testing
- Approximation algorithms for NP-complete problems on planar graphs
- The Complexity of Multiterminal Cuts
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Notions of metric dimension of corona products: combinatorial and computational results
- Landmarks in graphs
- Approximation complexity of metric dimension problem
- Title not available (Why is that?)
- Locating a robber on a graph via distance queries
- Computing the metric dimension for chain graphs
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Bidimensionality: new connections between FPT algorithms and PTASs
- Metric dimension of bounded width graphs
- The (weighted) metric dimension of graphs: hard and easy cases
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (24)
- Metric dimension parameterized by max leaf number
- Computing metric dimension of two types of claw-free cubic graphs with applications
- Approximation complexity of metric dimension problem
- Metric dimension of directed graphs
- The (weighted) metric dimension of graphs: hard and easy cases
- Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- Metric dimension parameterized by treewidth
- A note on the complexity of \(k\)\textsc{-metric dimension}
- Alternative parameterizations of \textsc{Metric Dimension}
- Computing a metric basis of a bipartite distance-hereditary graph
- On finding the best and worst orientations for the metric dimension
- On approximation complexity of metric dimension problem
- Computing the \(k\)-metric dimension of graphs
- Computing a metric basis of a 2-connected bipartite distance-hereditary graph
- On metric dimension of plane graphs $\mathfrak{J}_{n}$, $\mathfrak{K}_{n}$ and $\mathfrak{L}_{n}$
- Metric dimension: from graphs to oriented graphs
- Local metric dimension for graphs with small clique numbers
- On the Complexity of Metric Dimension
- The Plancherel measure for polygonal graphs
- Metric dimension of maximal outerplanar graphs
- Sequential metric dimension
- On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
- Hardness of metric dimension in graphs of constant treewidth
This page was built for publication: Complexity of metric dimension on planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q314819)
