Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

DOI10.1137/22m1510911arXiv2206.15424MaRDI QIDQ6072291

Fionn Mc Inerney, Esther Galby, Prafullkumar Tale, Unnamed Author, Roohani Sharma

Publication date: 13 October 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2206.15424

zbMATH Keywords

feedback vertex setmetric dimensionFPT algorithmstructural parameterization\textsf{W}[1-hardness]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Algorithms in computer science (68W99)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm for metric dimension of cactus block graphs
• Complexity of metric dimension on planar graphs
• The (weighted) metric dimension of graphs: hard and easy cases
• Centroidal localization game
• Adaptive identification in graphs
• Resolvability in graphs and the metric dimension of a graph
• Localization game on geometric and planar graphs
• Metric dimension parameterized by treewidth
• Computing a metric basis of a bipartite distance-hereditary graph
• Hardness of metric dimension in graphs of constant treewidth
• Truncated metric dimension for finite graphs
• Alternative parameterizations of \textsc{Metric Dimension}
• Low-dimensional representation of genomic sequences
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Locating a robber with multiple probes
• Metric Dimension Parameterized by Max Leaf Number
• Metric bases in digital geometry
• Domination and location in acyclic graphs
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• Structure-activity maps for visualizing the graph variables arising in drug design
• On a new class of codes for identifying vertices in graphs
• Centroidal bases in graphs
• Metric Dimension of Bounded Tree-length Graphs
• Parameterized Algorithms
• Sequential metric dimension
• Metric dimension: from graphs to oriented graphs
• Exploring the gap between treedepth and vertex cover through vertex integrity

This page was built for publication: Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters