Parameterized algorithms for locating-dominating sets

DOI10.1016/J.TCS.2025.115641MaRDI QIDQ6884330zbMATH OpenFDO

Authors Márcia R. Cappelle, Guilherme C. M. Gomes, Vinícius F. dos Santos

Publication date 15 December 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115641

zbMATH Keywords

dominating setkernelizationparameterized complexity

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• A tight approximation algorithm for the cluster vertex deletion problem
• Alternative parameterizations of \textsc{Metric Dimension}
• Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
• Domination and location in acyclic graphs
• Graph classes with structured neighborhoods and algorithmic applications
• scientific article; zbMATH DE number 3906528 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• Infeasibility of instance compression and succinct PCPs for NP
• Kernelization. Theory of parameterized preprocessing
• Linear-time algorithms for three domination-based separation problems in block graphs
• Locating domination in bipartite graphs and their complements
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• On problems without polynomial kernels
• On the complexity of k-SAT
• Optimal bounds on codes for location in circulant graphs
• Parameterized algorithms
• Parameterized algorithms for locating-dominating sets
• Parameterized complexity of vertex colouring
• Slightly superexponential parameterized problems
• Some consequences of non-uniform conditions on uniform classes
• Spanning Trees with Many Leaves
• Structural parameterization of locating-dominating set and test cover
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Twin-width. I: Tractable FO model checking
• Which problems have strongly exponential complexity?

Cited in

(1)

• Tight (double) exponential bounds for identification problems: locating-dominating set and test cover

This page was built for publication: Parameterized algorithms for locating-dominating sets

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