Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs

被引：9
作者：
Yeh, HG
Chang, GJ
机构：
[1] Natl Chiao Tung Univ, Dept Appl Math, Hsinchu 30050, Taiwan
[2] Natl Cent Univ, Dept Math, Chungli 320, Taiwan
来源：
THEORETICAL COMPUTER SCIENCE | 2001年 / 263卷 / 1-2期
关键词：
distance-hereditary graph; connected k-domination; k-dominating clique; algorithm;
D O I：
10.1016/S0304-3975(00)00225-5
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A graph is distance-hereditary if the distance between any two vertices in a connected induced subgraph is the same as in the original graph. This paper presents efficient algorithms for solving the weighted connected k-domination and the weighted k-dominating clique problems in distance-hereditary graphs, (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：3 / 8
页数：6
相关论文
共 22 条
[1]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[2]   DISTANCE-HEREDITARY GRAPHS [J].
BANDELT, HJ ;
MULDER, HM .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1986, 41 (02) :182-208
[3]  
Brandstadt A, 1998, NETWORKS, V31, P177, DOI 10.1002/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO
[4]  
2-C
[5]   ON DOMINATION PROBLEMS FOR PERMUTATION AND OTHER GRAPHS [J].
BRANDSTADT, A ;
KRATSCH, D .
THEORETICAL COMPUTER SCIENCE, 1987, 54 (2-3) :181-198
[6]   The algorithmic use of hypertree structure and maximum neighbourhood orderings [J].
Brandstadt, A ;
Chepoi, VD ;
Dragan, FF .
DISCRETE APPLIED MATHEMATICS, 1998, 82 (1-3) :43-77
[7]   LABELING ALGORITHMS FOR DOMINATION PROBLEMS IN SUN-FREE CHORDAL GRAPHS [J].
CHANG, GJ .
DISCRETE APPLIED MATHEMATICS, 1988, 22 (01) :21-34
[8]   THE K-DOMINATION AND K-STABILITY PROBLEMS ON SUN-FREE CHORDAL GRAPHS [J].
CHANG, GJ ;
NEMHAUSER, GL .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03) :332-345
[9]   DOMINATING CLIQUES IN GRAPHS [J].
COZZENS, MB ;
KELLEHER, LL .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :101-116
[10]   DISTANCE-HEREDITARY GRAPHS, STEINER TREES, AND CONNECTED DOMINATION [J].
DATRI, A ;
MOSCARINI, M .
SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :521-538
123