\(k\) -Power domination in block graphs

详细信息    查看全文

• 作者：Chao Wang ; Lei Chen ; Changhong Lu
• 关键词：Domination ; Power domination ; Electrical network monitoring ; Block graphs ; 05C69 ; 05C85 ; 68R10
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：865-873
• 全文大小：393 KB
• 参考文献：Aazami A (2010) Domination in graphs with bounded propagation: algorithms, and hardness results. J Comb Optim 19:429–456
  Aazami A, Stilp MD (2009) Approximation algorithms and hardness for domination with propagation. SIAM J Discret Math 23:1382–1399MathSciNet CrossRef MATH
  Baldwin TL, MiLi L, Boisen MB Jr, Adapa A (1993) Power system observability with minimal phasor measurement placement. IEEE Trans Power Syst 8:707–715CrossRef
  Chang GJ (1998) Algorithmic aspects of domination in graphs. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization, vol 3. Kluwer Academic Publishers, Boston
  Chang GJ (1989) Total domination in block graphs. Oper Res Lett 8:53–57MathSciNet CrossRef MATH
  Chang GJ, Dorbec P, Montassier M, Raspaud A (2012) Generalized power domination of graphs. Discret Appl Math 160:1691–1698MathSciNet CrossRef MATH
  Chang GJ, Nemhauser GL (1982) \(R\) -domination on block graphs. Oper Res Lett 1:214–218MathSciNet CrossRef MATH
  Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457–470MathSciNet CrossRef MATH
  Chen L, Lu C, Zeng Z (2009) A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inf Process Lett 110:20–23MathSciNet CrossRef MATH
  Cockayne EJ, Goodman SE, Hedetniemi ST (1975) A linear algorithm for the domination number of a tree. Inf Process Lett 4:41–44CrossRef MATH
  Dirac GA (1961) On rigid circuit graphs. Abh Math Sem Univ Hamburg 25:71–76MathSciNet CrossRef MATH
  Dorbec P, Henning MA, Lowenstein C, Montassier M, Raspaud A (2013) Generalized power domination in regular graphs. SIAM J Discret Math 27:1559–1574MathSciNet CrossRef MATH
  Dorbec P, Mollard M, Klavžar S, Špacapan S (2008) Power domination in product graphs. SIAM J Discret Math 22:554–567CrossRef MATH
  Dorfling M, Henning MA (2006) A note on power domination in grid graphs. Discret Appl Math 154:1023–1027MathSciNet CrossRef MATH
  Guo J, Niedermeier R, Raible D (2008) Improved algorithms and complexity results for power domination in graphs. Algorithmica 52:177–202MathSciNet CrossRef MATH
  Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998) Fundamentals of domination in graphs. Marcel Dekker, New YorkMATH
  Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998) Domination in graphs: advanced topics. Marcel Dekker, New YorkMATH
  Haynes TW, Hedetniemi SM, Hedetniemi ST, Henning MA (2002) Domination in graphs applied to electric power networks. SIAM J Discret Math 15:519–529MathSciNet CrossRef MATH
  Kneis J, Molle D, Richter S, Rossmanith P (2006) Parameterized power domination complexity. Inform Process Lett 98:145–149MathSciNet CrossRef MATH
  Liao CS, Lee DT (2005) Power domination problem in graphs. In: Proceedings of 11th Annual International Conference, COCOON 2005, Kunming, China, 2005, In: Lecture notes in computer science, vol 3595, pp 818–828
  Liao CS, Lee DT (2013) Power domination in circular-arc graphs. Algorithmica 65:443–466MathSciNet CrossRef MATH
  Wimer TV (1987) Linear algorithms on \(k\) -terminal graphs, Ph.D. Thesis, Clemson University
  Xu G, Kang L (2011) On the power domination number of the generalized Petersen graphs. J Comb Optim 22:282–291MathSciNet CrossRef MATH
  Xu G, Kang L, Shan E, Zhao M (2006) Power domination in block graphs. Theor Comput Sci 359:299–305MathSciNet CrossRef MATH
  Yen WCK (2003) The bottleneck independent domination on the classes of bipartite graphs and block graphs. Inf Sci 157:199–215CrossRef MATH
  
• 作者单位：Chao Wang (1)
  Lei Chen (2)
  Changhong Lu (1)
  
  1. Department of Mathematics, Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai, 200062, China
  2. College of Information Engineering, Shanghai Maritime University, Shanghai, 201306, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

The power system monitoring problem asks for as few as possible measurement devices to be put in an electric power system. The problem has a graph theory model involving power dominating set in graphs. The concept of \(k\)-power domination, first introduced by Chang et al. (Discret Appl Math 160:1691–1698, 2012), is a common generalization of domination and power domination. In this paper, we present a linear-time algorithm for \(k\)-power domination in block graphs. Keywords Domination Power domination Electrical network monitoring Block graphs