Nordic Journal of Computing Bibliography

Jan Arne Telle. Complexity of domination-type problems in graphs. Nordic Journal of Computing, 1(1):157-171, Spring 1994.
Abstract

Many graph parameters are the optimal value of an objective function over selected subsets S of vertices with some constraint on how many selected neighbors vertices in S, and vertices not in S, can have. Classic examples are minimum dominating set and maximum independent set. We give a characterization of these graph parameters that unifies their definitions, facilitates their common algorithmic treatment and allows for their uniform complexity classification. This characterization provides the basis for a taxonomy of domination-type and independence-type problems. We investigate the computational complexity of problems within this taxonomy, identify classes of NP-complete problems and classes of problems solvable in polynomial time.

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

Selected papers that cite this one

Selected references


Shortcuts:

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