|
|||||
|
|
Improved bottleneck domination algorithms |
|
| Authors: | Ton Kloks Dieter Kratsch Jiping Liu |
| Institution: | a Department of Mathematics and Computer Science, The University of Lethbridge, Alta, Canada T1K 3M4 b Université de Metz, LITA, 57045 Metz, Cedex 01, France c Department of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan |
| Abstract: | W.C.K. Yen introduced BOTTLENECK DOMINATION and BOTTLENECK INDEPENDENT DOMINATION. He presented an  -time algorithm to compute a minimum bottleneck dominating set. He also obtained that the BOTTLENECK INDEPENDENT DOMINATING SET problem is NP-complete, even when restricted to planar graphs.We present simple linear time algorithms for the BOTTLENECK DOMINATING SET and the BOTTLENECK TOTAL DOMINATING SET problem. Furthermore, we give polynomial time algorithms (most of them with linear time-complexities) for the BOTTLENECK INDEPENDENT DOMINATING SET problem on the following graph classes: AT-free graphs, chordal graphs, split graphs, permutation graphs, graphs of bounded treewidth, and graphs of clique-width at most k with a given k-expression. |
| Keywords: | Bottleneck domination Bottleneck independent domination AT-free graphs Chordal graphs Permutation graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |