On the parameterized complexity of approximating dominating set.

Karthik C. S.Bundit Laekhanukit Pasin Manurangsi

Published in: STOC (2018)

Keyphrases

dominating set
parameterized complexity
facility location problem
connected dominating set
global constraints
fixed parameter tractable
approximation algorithms
symmetry breaking
computational complexity
lower bound
linear programming
constraint programming
bounded treewidth