Optimal dynamic program for r-domination problems over tree decompositions

DOI10.4230/LIPIcs.IPEC.2016.8zbMath1398.68389arXiv1502.00716OpenAlexW2964157411MaRDI QIDQ4634391

Glencora Borradaile, Hung Le

Publication date: 10 April 2018

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

zbMATH Keywords

dynamic programmingexponential time hypothesis\(r\)-dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items (13)

Fast Algorithms for Join Operations on Tree Decompositions ⋮ A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph ⋮ New Results on Directed Edge Dominating Set ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Structurally parameterized \(d\)-scattered set ⋮ Unnamed Item ⋮ A generic convolution algorithm for join operations on tree decompositions

This page was built for publication: Optimal dynamic program for r-domination problems over tree decompositions