| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419985 | Discrete Applied Mathematics | 2007 | 10 Pages |
Abstract
We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n)O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n))O(m(m+n)) time.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T.C.E. Cheng, L.Y. Kang, C.T. Ng,