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 [J].

BALDWIN, TL ;

MILI, L ;

BOISEN, MB ;

ADAPA, R .

IEEE TRANSACTIONS ON POWER SYSTEMS, 1993, 8 (02) :707-715

[2] Generalized power domination of graphs [J].

Chang, Gerard Jennhwa ;

Dorbec, Paul ;

Montassier, Mickael ;

Raspaud, Andre .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (12) :1691-1698

[3] The k-power domination problem in weighted trees [J].

Cheng, Changjie ;

Lu, Changhong ;

Zhou, Yu .

THEORETICAL COMPUTER SCIENCE, 2020, 809 :231-238

[4] A note on power domination in grid graphs [J].

Dorfling, M ;

Henning, MA .

DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) :1023-1027

[5] TRANSVERSALS IN 5-UNIFORM HYPERGRAPHS AND TOTAL DOMINATION IN GRAPHS WITH MINIMUM DEGREE FIVE [J].

Dorfling, Michael ;

Henning, Michael A. .

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 [J].

Haynes, TW ;

Hedetniemi, SM ;

Hedetniemi, ST ;

Henning, MA .

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 →