Computing a metric basis of a 2-connected bipartite distance-hereditary graph

DOI10.1016/J.TCS.2019.11.031MaRDI QIDQ2283041zbMATH OpenOpenAlexWikidataFDO

Authors Marina Moscarini

Publication date 27 December 2019

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

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

zbMATH Keywords

bipartite graphdistance-hereditary graphhomogeneous metric sethomogeneous setmetric basismetric generator

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Computing a metric basis of a bipartite distance-hereditary graph
• Computing the Metric Dimension by Decomposing Graphs into Extended Biconnected Components
• Computing the metric dimension for chain graphs
• The strong dimension of distance-hereditary graphs
• Computing the \(k\)-metric dimension of graphs

Cites work

• A linear time algorithm for metric dimension of cactus block graphs
• Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
• Complexity of metric dimension on planar graphs
• Computing the metric dimension for chain graphs
• Computing the metric dimension of a graph from primary subgraphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• scientific article; zbMATH DE number 4060740 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• On the Metric Dimension of Cartesian Products of Graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• The metric dimension of two-dimensional extended meshes
• The strong dimension of distance-hereditary graphs

Cited in

(5)

• Computing a metric basis of a bipartite distance-hereditary graph
• Learning to compute the metric dimension of graphs
• Graphs with metric dimension two - a characterization
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• The Weisfeiler-Leman dimension of distance-hereditary graphs

This page was built for publication: Computing a metric basis of a 2-connected bipartite distance-hereditary graph

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