Alternative parameterizations of \textsc{Metric Dimension}

DOI10.1016/j.tcs.2019.01.028zbMath1436.68146arXiv1804.10670OpenAlexW2962811261WikidataQ128456782 ScholiaQ128456782MaRDI QIDQ2285127

M. S. Ramanujan, Magnus Wahlström, Felix Reidl, Gregory Gutin

Publication date: 16 January 2020

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

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

zbMATH Keywords

graphkernelmetric dimensionfixed-parameter tractable

Mathematics Subject Classification ID

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

Related Items (5)

On vertices contained in all or in no metric basis ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters ⋮ On the status sequences of trees ⋮ On metric dimensions of hypercubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The difference between the metric dimension and the determining number of a graph
• Complexity of metric dimension on planar graphs
• Kernelization using structural parameters on sparse graph classes
• Fundamentals of parameterized complexity
• The (weighted) metric dimension of graphs: hard and easy cases
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Solving MAX-\(r\)-SAT above a tight lower bound
• Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
• Almost 2-SAT is fixed-parameter tractable
• The NP-completeness of the bandwidth minimization problem
• 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
• (Non-)existence of polynomial kernels for the test cover problem
• A completeness theory for polynomial (Turing) kernelization
• Computing the metric dimension for chain graphs
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Landmarks in graphs
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Kernelization – Preprocessing with a Guarantee
• Parameterized Study of the Test Cover Problem
• Metric Dimension Parameterized by Max Leaf Number
• Kernelization
• Kernelization Lower Bounds Through Colors and IDs
• Kernelization Lower Bounds by Cross-Composition
• Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results
• Metric Dimension of Bounded Tree-length Graphs
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Parameterized Algorithms
• Partially Polynomial Kernels for Set Cover and Test Cover
• The metric dimension of the lexicographic product of graphs

This page was built for publication: Alternative parameterizations of \textsc{Metric Dimension}