Metric Dimension of Bounded Width Graphs

DOI10.1007/978-3-662-48054-0_10zbMath1466.68054OpenAlexW2276402578WikidataQ56551545 ScholiaQ56551545MaRDI QIDQ2946381

Fedor V. Fomin, Petr A. Golovach, M. S. Ramanujan, Rémy Belmonte

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_10

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (8)

Iterated Type Partitions ⋮ Complexity of metric dimension on planar graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ The threshold dimension of a graph ⋮ To Approximate Treewidth, Use Treelength! ⋮ The threshold dimension and threshold strong dimension of a graph: a survey ⋮ The threshold dimension and irreducible graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A survey of the algorithmic aspects of modular decomposition
• On the complexity of computing treelength
• Treewidth. Computations and approximations
• Treewidth for graphs with small chordality
• Resolvability in graphs and the metric dimension of a graph
• Tree-decompositions with bags of small diameter
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Parametrized complexity theory.
• Landmarks in graphs
• Parameterized Algorithms for Modular-Width
• On the Complexity of Metric Dimension
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
• Transitiv orientierbare Graphen

This page was built for publication: Metric Dimension of Bounded Width Graphs