Nordic Journal of Computing Bibliography

Pinar Heggernes and Jan Arne Telle. Partitioning Graphs into Generalized Dominating Sets. Nordic Journal of Computing, 5(2):128-142, Summer 1998.

We study the computational complexity of partitioning the vertices of a graph into generalized dominating sets. Generalized dominating sets are parameterized by two sets of nonnegative integers sigma and rho which constrain the neighborhood N(v) of vertices. A set S of vertices of a graph is said to be a (sigma, rho)-set if forall v in S: |N(v) intersect S| in sigma and forall v not in S: |N(v) intersect S | in rho. The (k, sigma, rho )-partition problem asks for the existence of a partition V1, V2,...,Vk of vertices of a given graph G such that Vi, i=1,2,...,k is a (sigma, rho)-set of G. We study the computational complexity of this problem as the parameters sigma, rho and k vary.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: graph partitioning, NP-completeness, complexity, domination

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database