Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs.
Chunmei LiuYinglei SongPublished in: J. Comb. Optim. (2011)
Keyphrases
- dominating set
- connected dominating set
- undirected graph
- approximation algorithms
- parameterized complexity
- facility location problem
- bounded treewidth
- minimum cost
- spanning tree
- fixed parameter tractable
- directed graph
- connected components
- worst case
- np hard
- decision making
- weighted graph
- continuous variables
- facility location
- metaheuristic
- search algorithm