Hardness of r-dominating set on Graphs of Diameter (r + 1)

DOI10.1007/978-3-319-03898-8_22zbMath1406.68042OpenAlexW136930666MaRDI QIDQ2867088

Saket Saurabh, M. S. Ramanujan, Geevarghese Philip, Neeldhara Misra, Daniel Lokshtanov

Publication date: 10 December 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03898-8_22

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Colouring a dominating set without conflicts: \(q\)-subset square colouring ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ The parameterized complexity of terminal monitoring set ⋮ Unnamed Item ⋮ Revising Johnson's table for the 21st century ⋮ Coloring a dominating set without conflicts: \(q\)-subset square coloring

This page was built for publication: Hardness of r-dominating set on Graphs of Diameter (r + 1)