Paired domination on interval and circular-arc graphs |
| |
| Authors: | TCE Cheng CT Ng |
| |
| Institution: | 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 等数据库收录！ |
|
