|
|||||
|
|
Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs |
|
| Authors: | JMJ Mark Keil and Patrice Belleville |
| Institution: | a Department of Computer Science, University of Saskatchewan, 57 Campus Drive, Saskatoon, Saskatchewan, Canada S7N 5A9 b Department of Computer Science, University of British Columbia, # 201-2366 Main Mall, Vancouver, BC, Canada V6T 1Z4 |
| Abstract: | We investigate the complexity of several domination problems on the complements of bounded tolerance graphs and the complements of trapezoid graphs. We describe an O(n2 log5 n) time and O(n2) space algorithm to solve the domination problem on the complement of a bounded tolerance graph, given a square embedding of that graph. We also prove that domination, connected domination and total domination are all NP-complete on co-trapezoid graphs. |
| Keywords: | Dominating set Comparability graph Bounded tolerance graph Trapezoid graph |
| 本文献已被 ScienceDirect 等数据库收录！ | |