AT-free图的配对控制集算法

Algorithm for the Paired-dominating Set Problem on AT-free Graphs

下载PDF

导出

摘要本文给出了配对控制集在AT-free图的BFS-树上分布的结构性质．利用这些性质,我们给出了求解AT-free图类最小配对控制集的多项式时间算法． In this paper, we give the distributed structural property of the paired-dominating set on the BFS-tree of an AT-free graph. Applying the structural property, we present a polynomial time algorithm to compute a minimum cardinality paired-dominating set on AT-free graphs.

作者许光俊康丽英皮军德

机构地区上海大学数学系

出处《运筹学学报》 CSCD 北大核心 2005年第4期60-66,共7页 Operations Research Transactions

基金国家自然科学基金资助课题(10101010)上海市重点学科建设资助项目上海市教委青年科学基金资助项目(01QN6262).

关键词运筹学 AT-free图类配对控制集算法 Operations research, AT-free graph, paired-dominating set, algorithm

分类号 O157.5 [理学—基础数学]

引文网络
相关文献

参考文献12

1H. Balakrishnan, R. Rajaraman, C. Pnadu Rangan. Connected domination and steiner set on asteroidal triple-free graphs, Proceedings of WADS'93, Lecture Notes in Computer Science,Vol.709, Springer, Berlin, 1993, pp.131～141.
2H. Broersma, T. Kloks, D. Kratsch, H. Müiller. Independent sets in asteroidal triple-free graphs, Proceedings of ICALP'97, Lecture Notes in Computer Science, Vol.1256, Springer,Berlin, 1997, pp.760～770.
3D.G. Corneil, S. Olariu, L. Stewart. A linear time algorithm to compute a dominating path in an AT-free graph. Inform. Process. Lett., 1995, 54: 253～258.
4D.G. Corneil, S. Olariu, L. Stewart. Asteroidal triple-free graphs. SIAM J. Discrete Math.,1997, 10: 399～430.
5D.G. Corneil, S. Olariu, L. Stewart. Linear time algorithms for dominating pairs in asteroidal triple-free graphs. SIAM J. Comput., 1999, 28: 1284～1297.
6T.W. Haynes, S.T. Hedetniemi and P.J. Slater. Fundamentals of Domination in Graphs [M].New York: Marcel Dekker, 1998.
7T.W. Haynes, S.T. Hedetniemi and P.J. Slater. Domination in Graphs: Advanced Topics [M].New York: Marcel Dekker, 1998.
8T.W. Haynes, P.J. Slater. Paired-domination in graphs. Networks, 1998, 32: 199～206.
9T. Kloks, D. Kratsch, H. Müller. Approximating the bandwidth for AT-free graphs. Journal of Algorithms, 1999, 32: 41～57.
10D. Kratsch. Domination and total domination on asteroidal triple-free graphs. Discrete Appl.Math., 2000, 99: 111～123.

1黄海圆,马美杰.路与圈的笛卡尔乘积的配对控制数[J].浙江师范大学学报（自然科学版）,2015,38(2):172-175. 被引量：3
2皮军德,林浩.直线簇上区间图的最小全控制集和最小配对控制集[J].河南科学,2007,25(4):537-541.

运筹学学报

2005年第4期

浏览历史

内容加载中请稍等...

AT-free图的配对控制集算法

参考文献12

相关作者

相关机构

相关主题

浏览历史