Computer Science – Computational Complexity
Scientific paper
2010-04-15
Computer Science
Computational Complexity
Preceding version contained several flaws; this version correct them
Scientific paper
The concept of generalized domination unifies well-known variants of domination-like problems. A generalized domination (also called [Sigma,Rho]-domination) problem consists in finding a dominating set for which every vertex of the input graph is satisfied, given two sets of constraints Sigma and Rho. Very few problems are known to be W[1]-hard when restricted to graphs of bounded tree-width. We exhibit here a large new (infinite) collection of W[1]-hard problems parameterized by the tree-width of the input graph, that is [Sigma,Rho]-domination when Sigma is a set with arbitrary large gaps between two consecutive elements and Rho is cofinite (and an additional technical constraint on Sigma).
No associations
LandOfFree
Parameterized Complexity of Generalized Domination Problems on Bounded Tree-Width Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Parameterized Complexity of Generalized Domination Problems on Bounded Tree-Width Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Complexity of Generalized Domination Problems on Bounded Tree-Width Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380210