Nordic Journal of Computing Bibliography

P. Eades, M. Keil, P. D. Manuel, and M. Miller. Two Minimum Dominating Sets with Minimum Intersection in Chordal Graphs. Nordic Journal of Computing, 3(3):220-237, Fall 1996.
Abstract

We prove that the problem of finding two minimum dominating sets (connected dominating sets or clique transversals) with minimum intersection is polynomially solvable on interval graphs. Furthermore, the problem of deciding whether or not there exist two disjoint minimum dominating sets (connected dominating sets or clique transversals) is shown to be NP-hard for chordal graphs.

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: chordal graph, interval graph, dominating set, clique transversal

Selected references


Shortcuts:

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