Computing the metric dimension for chain graphs

DOI10.1016/J.IPL.2015.04.006zbMATH Open1329.05095OpenAlexW2071116170WikidataQ56551558 ScholiaQ56551558MaRDI QIDQ2346556FDOQ2346556

Authors: Henning Fernau, Pinar Heggernes, Pim Van 't Hof, Daniel Meister, Reza Saei 

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

Recommendations

• Metric dimension and its variations of chain graphs
• Computing the \(k\)-metric dimension of graphs
• Computing the metric dimension of wheel related graphs
• Computing the metric dimension of gear graphs
• The metric dimension and girth of graphs
• On the metric dimension of a graph
• The Metric Dimension of Circulant Graphs
• Computing the metric dimension of a graph from primary subgraphs
• Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components

zbMATH Keywords

metric dimensioncombinatorial problemschain graphspolynomial-time algorithmsadjacency metric dimension

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Graph Classes: A Survey
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Resolvability in graphs and the metric dimension of a graph
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• On classes of regular graphs with constant metric dimension
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• 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
• On the Complexity of Metric Dimension
• Title not available (Why is that?)
• Approximation complexity of metric dimension problem
• The independent resolving number of a graph
• On Metric Generators of Graphs
• The metric dimension of the lexicographic product of graphs
• Title not available (Why is that?)
• The metric dimension of Cayley digraphs
• Mastermind
• The (weighted) metric dimension of graphs: hard and easy cases

Cited In (26)

• Metric dimension parameterized by max leaf number
• Computing the metric dimension of gear graphs
• Metric dimension and its variations of chain graphs
• A linear time algorithm for metric dimension of cactus block graphs
• Some invariants related to threshold and chain graphs
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Complexity of metric dimension on planar graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Metric dimension parameterized by treewidth
• Learning to compute the metric dimension of graphs
• Alternative parameterizations of \textsc{Metric Dimension}
• Linear-time algorithms for three domination-based separation problems in block graphs
• Optimal strategies for the static black-peg AB game with two and three pegs
• The metric dimension of \(\mathbb{Z}_n \times \mathbb{Z}_n \times \mathbb{Z}_n\) is \(\lfloor 3n/2 \rfloor \)
• Computing a metric basis of a bipartite distance-hereditary graph
• Computing the \(k\)-metric dimension of graphs
• Computing a metric basis of a 2-connected bipartite distance-hereditary graph
• On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs
• Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components
• Computing the metric dimension of a graph from primary subgraphs
• Metric dimension of maximal outerplanar graphs
• On metric dimension of edge comb product of vertex-transitive graphs
• Computing the metric dimension of kayak paddles graph and cycles with chord
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Hardness of metric dimension in graphs of constant treewidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2346556)