图的最小控制树问题

doi:10.13371/j.cnki.chin.q.j.m.2014.01.001

数学季刊 ›› 2014, Vol. 29 ›› Issue (1): 1-8.doi: 10.13371/j.cnki.chin.q.j.m.2014.01.001

• • 下一篇

图的最小控制树问题

1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University

收稿日期:2013-03-01 出版日期:2014-03-30 发布日期:2022-11-28
作者简介:LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.
基金资助:
Supported by NNSF of China (11101383,61373106)

Minimum Dominating Tree Problem for Graphs

1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University

Received:2013-03-01 Online:2014-03-30 Published:2022-11-28
About author:LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.
Supported by:
Supported by NNSF of China (11101383,61373106)

摘要/Abstract

摘要： A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

关键词: network optimization, minimum dominating tree, special graphs, exact evaluation

Abstract: A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

Key words: network optimization, minimum dominating tree, special graphs, exact evaluation

中图分类号:

O157.5

林浩, 林澜. 图的最小控制树问题[J]. 数学季刊, 2014, 29(1): 1-8.

LIN Hao, LIN Lan.

Minimum Dominating Tree Problem for Graphs [J]. Chinese Quarterly Journal of Mathematics, 2014, 29(1): 1-8.

[1]	刘树洋, 李峰. 强乘积图的最小强半径[J]. 数学季刊, 2024, 39(1): 68-72.
[2]	攸晓杰, 马海成, 张斌, 李雅兰. 两类四圈图的奇异性[J]. 数学季刊, 2023, 38(4): 349-359.
[3]	王世英, 赵丽娜. 在比较模型下网络是 n-邻 d-可诊断的充分条件[J]. 数学季刊, 2022, 37(4): 343-354.
[4]	林艺舒, 常彩冰, 刘岩. 图族和树族的带宽和割宽的遍历性[J]. 数学季刊, 2022, 37(4): 355-365.
[5]	张庆楠, 惠志昊, 杨雨, 王安. 哈林图的导出匹配可扩性[J]. 数学季刊, 2022, 37(4): 380-385.
[6]	李贝贝, 尚卫苹. 具有特定独立的罗马2-控制数的树[J]. 数学季刊, 2022, 37(4): 386-393.
[7]	张义冉, 王秀梅. 圈强迫的2-连通无爪三正则图的刻画#br# #br# [J]. 数学季刊, 2022, 37(4): 432-440.
[8]	夏伟皓, 石美, 肖明月, 蔡建生, 王纪辉. r-正则有向图的多数染色 [J]. 数学季刊, 2022, 37(2): 142-146.
[9]	白雨杰, 毋述斐. 一类三正则图的全友好指数集[J]. 数学季刊, 2021, 36(3): 221-234.
[10]	阴浩然, 李峰. 有向图强乘积的代数群性质[J]. 数学季刊, 2020, 35(4): 424-430.
[11]	何玉萍, 陈祥恩. mC₉的点可区别全染色的最优算法[J]. 数学季刊, 2019, 34(3): 242-258.
[12]	陈丽娜, 谢炎涛. 关于H-cordial图和semi-H-cordial图的若干结论[J]. 数学季刊, 2019, 34(1): 52-56.
[13]	周后卿. 循环图的距离能量[J]. 数学季刊, 2018, 33(3): 233-239.
[14]	张海良. 关于路与圈的匹配多项式的一个注记[J]. 数学季刊, 2018, 33(2): 140-143.
[15]	任云霞, 王世英. 局部扭立方的1好邻连通度和诊断度[J]. 数学季刊, 2017, 32(4): 371-381.

图的最小控制树问题

Minimum Dominating Tree Problem for Graphs

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价