Parameterized dominating set problem in chordal graphs: complexity and lower bound.
Chunmei LiuYinglei SongPublished in: J. Comb. Optim. (2009)
Keyphrases
- dominating set
- lower bound
- connected dominating set
- upper bound
- worst case
- facility location problem
- undirected graph
- objective function
- directed graph
- decision problems
- graph matching
- computational complexity
- lower and upper bounds
- np hard
- vc dimension
- weighted graph
- lagrangian relaxation
- branch and bound algorithm
- linear program