Computing the metric dimension for chain graphs

DOI10.1016/j.ipl.2015.04.006zbMath1329.05095OpenAlexW2071116170WikidataQ56551558 ScholiaQ56551558MaRDI QIDQ2346556

Daniel Meister, Pim van 't Hof, Pinar Heggernes, Reza Saei, Henning Fernau

Publication date: 2 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.04.006

zbMATH Keywords

combinatorial problemschain graphspolynomial-time algorithmsmetric dimensionadjacency metric dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Complexity of metric dimension on planar graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Linear-time algorithms for three domination-based separation problems in block graphs ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Computing the \(k\)-metric dimension of graphs ⋮ Computing the metric dimension of a graph from primary subgraphs ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ The metric dimension of \(\mathbb{Z}_n \times \mathbb{Z}_n \times \mathbb{Z}_n\) is \(\lfloor 3n/2 \rfloor \) ⋮ Metric dimension parameterized by treewidth ⋮ Metric dimension of maximal outerplanar graphs ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Hardness of metric dimension in graphs of constant treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On classes of regular graphs with constant metric dimension
• Approximation complexity of metric dimension problem
• Mastermind
• The metric dimension of Cayley digraphs
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Resolvability in graphs and the metric dimension of a graph
• Landmarks in graphs
• On the Complexity of Metric Dimension
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Graph Classes: A Survey
• The independent resolving number of a graph
• Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results
• The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
• On Metric Generators of Graphs
• The metric dimension of the lexicographic product of graphs

This page was built for publication: Computing the metric dimension for chain graphs