Power domination with bounded time constraints

详细信息    查看全文

• 作者：Chung-Shou Liao
• 关键词：Algorithm ; Domination ; Power domination ; Time constraint
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：31
• 期：2
• 页码：725-742
• 全文大小：618 KB
• 参考文献：Aazami A, Stilp MD (2009) Approximation algorithms and hardness for domination with propagation. SIAM J Discret Math 23(3):1382–1399MathSciNet CrossRef MATH
  Aazami A (2010) Domination in graphs with bounded propagation: algorithms, formulation and hardness results. J Comb Optim 19(4):429–456MathSciNet CrossRef MATH
  Atkins D, Haynes TW, Henning MA (2006) Placing monitoring devices in electric power networks modeled by block graphs. Ars Combinatoria 79:129–143MathSciNet MATH
  Baldwin TL, Mili L, Boisen MB Jr, Adapa R (1993) Power system observability with minimal phasor measurement placewement. IEEE Trans Power Syst 8(2):707–715CrossRef
  Brueni DJ, Heath LS (2005) The PMU placement problem. SIAM J Discret Math 19(3):744–761MathSciNet CrossRef MATH
  Chang GJ (1998) Algorithmic aspects of domination in graphs. In: Du D-Z , Pardalos PM (eds) Handbook of Combinatorial Optimization vol 3, pp 339–405
  Chang CL, Lyuu YD (2008) Spreading messages. In: Proceedings of the 14th international conference on computing and combinatorics. LNCS, vol 5092, pp 587–599
  Chang GJ, Dorbec P, Montassier M, Raspaud A (2012) Generalized power domination of graphs. Discret Appl Math 160:1691–1698MathSciNet CrossRef MATH
  Chien Y-Y (2004) Power domination on graphs. Master thesis, Department Mathematics, National Taiwan University, Taiwan
  Dorbec P, Mollard M, Klavžar S, Špacapan S (2008) Power domination in product graphs. SIAM J Discret Math 22(2):554–567CrossRef MATH
  Dorbec P, Henning MA, Lowenstein C, Montassier M, Raspaud A (2013) Generalized power domination in regular graphs. SIAM J Discret Math 27(3):1559–1574MathSciNet CrossRef MATH
  Dorfling M, Henning MA (2006) A note on power domination in grid graphs. Discret Appl Math 154(6):1023–1027MathSciNet CrossRef MATH
  Feige U (1998) A threshold of ln \(n\) for approximating set cover. J ACM 45(4):634–652MathSciNet CrossRef MATH
  Guo J, Niedermeier R, Raible D (2008) Improved algorithms and complexity results for power domination in graphs. Algorithmica 52(2):177–202MathSciNet CrossRef MATH
  Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: the theory. Marcel Dekker Inc, New York
  Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in graphs: advanced topics. Marcel Dekker Inc, New York
  Haynes TW, Hedetniemi SM, Hedetniemi ST, Henning MA (2002) Domination in graphs applied to electric power networks. SIAM J Discret Math 15(4):519–529MathSciNet CrossRef MATH
  Hedetniemi ST, Hedetniemi SM, Liestman AL (1988) A survey of broadcasting and gossiping in communication networks. Networks 18:319–349MathSciNet CrossRef MATH
  Karp R, Schindelhauer C, Shenker S, Vocking B (2000) Randomized rumor spreading. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Foundations Computer Science (FOCS), pp 565–574
  Kneis J, Mölle D, Richter S, Rossmanith P (2006) Parameterized power domination complexity. Info Process Lett 98(4):145–149CrossRef MATH
  Liao C-S, Lee DT (2011) Power domination in circular-arc graphs. Algorithmica 65(2):443-466
  Liao C-S (2009) Graph-theoretic domination and related problems with applications. Doctoral thesis, Dept Computer Science and Information Engineering, National Taiwan University, Taiwan
  Liao C-S, Lee DT (2005) Power domination problem in graphs. In: Proceedings of the 11th annual international conference on computing and combinatorics. LNCS, vol 3595, pp 818–828
  Manousakis NM, Korres GN, Georgilakis PS (2012) Taxonomy of PMU placement methodologies. IEEE Trans Power Syst 27(2):1070–1077CrossRef
  Mili L, Baldwin TL, Phadke AG (1991) Phasor measurements for voltage and transient stability monitoring and control. In: Proceedings of the EPRI-NSF workshop on application of advanced mathematics to power system
  Monticelli A (2000) Electric power system state estimation. Proc IEEE 88(2):262–282CrossRef
  Nuqui RF, Phadke AG (2005) Phasor measurement unit placement techniques for complete and incomplete observability. IEEE Trans Power Delivery 20(4):2381–2388CrossRef
  Phadke AG (2002) Synchronized phasor measurements—a historical overview. In: Proceedings of the transmission and distribution conference and exhibition, pp 476–479
  Raible D, Fernau H (2012) An exact exponential time algorithm for power dominating set. Algorithmica 63(1–2):323–346MathSciNet CrossRef MATH
  Xu G, Kang L, Shan E, Zhao M (2006) Power domination in block graphs. Theoret Comput Sci 359:299–305MathSciNet CrossRef MATH
  Xu G, Kang L (2011) On the power domination number of the generalized Petersen graphs. J Comb Optim 22:282–291MathSciNet CrossRef MATH
  Xu B, Yoon YJ, Abur A (2005) Optimal placement and utilization of phasor measurements for state estimation. In Proceedings of the power system computation conference
  Zhao M, Kang L, Chang GJ (2006) Power domination in graphs. Discret Math 306(15):1812–1816MathSciNet CrossRef MATH
  Zhao M, Kang L (2007) Power domination in planar graphs with small diameter. J Shanghai Univ 11(3):218–222MathSciNet CrossRef MATH
  
• 作者单位：Chung-Shou Liao (1)
  
  1. Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, 30013, Taiwan
  
• 刊物类别：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

文摘

Based on the power observation rules, the problem of monitoring a power utility network can be transformed into the graph-theoretic power domination problem, which is an extension of the well-known domination problem. A set \(S\) is a power dominating set (PDS) of a graph \(G=(V,E)\) if every vertex \(v\) in \(V\) can be observed under the following two observation rules: (1) \(v\) is dominated by \(S\), i.e., \(v \in S\) or \(v\) has a neighbor in \(S\); and (2) one of \(v\)’s neighbors, say \(u\), and all of \(u\)’s neighbors, except \(v\), can be observed. The power domination problem involves finding a PDS with the minimum cardinality in a graph. Similar to message passing protocols, a PDS can be considered as a dominating set with propagation that applies the second rule iteratively. This study investigates a generalized power domination problem, which limits the number of propagation iterations to a given positive integer; that is, the second rule is applied synchronously with a bounded time constraint. To solve the problem in block graphs, we propose a linear time algorithm that uses a labeling approach. In addition, based on the concept of time constraints, we provide the first nontrivial lower bound for the power domination problem. Keywords Algorithm Domination Power domination Time constraint