Labeling algorithm for power domination problem of trees

被引：0

作者：

Lyu, Yijia ^{[1
]}

机构：

[1] East China Normal Univ, High Sch 2, Shanghai, Peoples R China

来源：

APPLIED MATHEMATICS AND COMPUTATION | 2023年 / 457卷

关键词：

Trees; Dominating set; Power domination; Linear-time algorithm; GRAPHS;

D O I：

10.1016/j.amc.2023.128163

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this paper, the power domination problem on trees is studied and we give a linear-time algorithm to it by using the labeling method. Our algorithm is simpler and easier to understand than those in [3,7]. & COPY; 2023 Elsevier Inc. All rights reserved.

引用

页数：4

共 10 条

[1] POWER-SYSTEM OBSERVABILITY WITH MINIMAL PHASOR MEASUREMENT PLACEMENT
BALDWIN, TL
MILI, L
BOISEN, MB
ADAPA, R
[J]. IEEE TRANSACTIONS ON POWER SYSTEMS, 1993, 8 (02) : 707 - 715
[2] Generalized power domination of graphs
Chang, Gerard Jennhwa
Dorbec, Paul
Montassier, Mickael
Raspaud, Andre
[J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) : 1691 - 1698
[3] The k-power domination problem in weighted trees
Cheng, Changjie
Lu, Changhong
Zhou, Yu
[J]. THEORETICAL COMPUTER SCIENCE, 2020, 809 : 231 - 238
[4] A note on power domination in grid graphs
Dorfling, M
Henning, MA
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) : 1023 - 1027
[5] TRANSVERSALS IN 5-UNIFORM HYPERGRAPHS AND TOTAL DOMINATION IN GRAPHS WITH MINIMUM DEGREE FIVE
Dorfling, Michael
Henning, Michael A.
[J]. QUAESTIONES MATHEMATICAE, 2015, 38 (02) : 155 - 180
[6] Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[7] Domination in graphs applied to electric power networks
Haynes, TW
Hedetniemi, SM
Hedetniemi, ST
Henning, MA
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2002, 15 (04) : 519 - 529
[8] Liao CS, 2005, LECT NOTES COMPUT SC, V3595, P818, DOI 10.1007/11533719_83
[9] MILI L, 1991, P EPRI NSF WORKSH AP
[10] Wang C, 2016, J COMB OPTIM, V31, P865, DOI 10.1007/s10878-014-9795-0

← 1 →