|
|||||
|
|
Paired domination on interval and circular-arc graphs |
|
| Authors: | T.C.E. Cheng C.T. Ng |
| Affiliation: | a Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong b Department of Mathematics, Shanghai University, Shanghai 200444, China |
| 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) 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)) time. |
| Keywords: | 05C69 05C85 68Q25 68R10 68W05 |
| 本文献已被 ScienceDirect 等数据库收录！ | |