nach oben

Journal of Combinatorial Optimization

Erschienen in:

23.01.2019

Connected power domination in graphs

verfasst von: Boris Brimkov, Derek Mikesell, Logan Smith

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The study of power domination in graphs arises from the problem of placing a minimum number of measurement devices in an electrical network while monitoring the entire network. A power dominating set of a graph is a set of vertices from which every vertex in the graph can be observed, following a set of rules for power system monitoring. In this paper, we study the problem of finding a minimum power dominating set which is connected; the cardinality of such a set is called the connected power domination number of the graph. We show that the connected power domination number of a graph is NP-hard to compute in general, but can be computed in linear time in cactus graphs and block graphs. We also give various structural results about connected power domination, including a cut vertex decomposition and a characterization of the effects of various vertex and edge operations on the connected power domination number. Finally, we present novel integer programming formulations for power domination, connected power domination, and power propagation time, and give computational results.

Vorheriger Artikel Non-adaptive group testing on graphs with connectivity

Nächster Artikel Determining the interset distance

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aazami A (2008) Hardness results and approximation algorithms for some problems on graphs. Ph.D. thesis, Ph.D. thesis. University of Waterloo

Aazami A (2010) Domination in graphs with bounded propagation: algorithms, formulations and hardness results. J Comb Optim 19(4):429–456MathSciNetCrossRefMATH

Aazami A, Stilp K (2009) Approximation algorithms and hardness for domination with propagation. SIAM J Discrete Math 23(3):1382–1399MathSciNetCrossRefMATH

AIM Special Work Group (2008) Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl 428(7):1628–1648MathSciNetCrossRef

Akhlaghi S, Zhou N, Wu NE (2016) PMU placement for state estimation considering measurement redundancy and controlled islanding. In: Power and Energy Society General Meeting (PESGM), pp 1–5

Aminifar F, Fotuhi-Firuzabad M, Shahidehpour M, Khodaei A (2011) Probabilistic multistage PMU placement in electric power systems. IEEE Trans Power Deliv 26(2):841–849CrossRef

Bader DA, Kappes A, Meyerhenke H, Sanders P, Schulz C, Wagner D (2014) Benchmarking for graph clustering and partitioning. In: Encyclopedia of social network analysis and mining. Springer, pp 73–82

Baldwin T, Mili L, Boisen M, Adapa R (1993) Power system observability with minimal phasor measurement placement. IEEE Trans Power Syst 8(2):707–715CrossRef

Barioli F, Fallat S, Hogben L (2004) Computation of minimal rank and path cover number for certain graphs. Linear Algebra Appl 392:289–303MathSciNetCrossRefMATH

Barioli F, Fallat S, Hogben L (2005) On the difference between the maximum multiplicity and path cover number for tree-like graphs. Linear Algebra Appl 409:13–31MathSciNetCrossRefMATH

Benson KF, Ferrero D, Flagg M, Furst V, Hogben L, Vasilevska V, Wissman B (2018) Power domination and zero forcing for graph products. Aust J Comb 70(2):221–235MATH

Bondy JA, Murty USR (1976) Graph theory with applications, vol 290. Macmillan, LondonCrossRefMATH

Bozeman C, Brimkov B, Erickson C, Ferrero D, Flagg M, Hogben L (2018) Restricted power domination and zero forcing problems. J Comb Optim, in press

Brimkov B, Fast CC, Hicks IV (2018) Computational approaches for zero forcing and related problems. Eur J Oper Res, in press

Brimkov B, Fast CC, Hicks IV (2017) Graphs with extremal connected forcing numbers. arXiv:1701.08500

Brimkov B, Hicks IV (2017) Complexity and computation of connected zero forcing. Discrete Appl Math 229:31–45MathSciNetCrossRefMATH

Brueni DJ (1993) Minimal PMU placement for graph observability: a decomposition approach. Ph.D. thesis, Virginia Tech

Brueni DJ, Heath LS (2005) The PMU placement problem. SIAM J Discrete Math 19(3):744–761MathSciNetCrossRefMATH

Burgarth D, Giovannetti V (2007) Full control by locally induced relaxation. Phys Rev Lett 99(10):100501CrossRef

Camby E, Cardinal J, Fiorini S, Schaudt O (2014) The price of connectivity for vertex cover. Discrete Math Theor Comput Sci 16:207–223MathSciNetMATH

Caro Y, West DB, Yuster R (2000) Connected domination and spanning trees with many leaves. SIAM J Discrete Math 13(2):202–211MathSciNetCrossRefMATH

Chang GJ, Dorbec P, Montassier M, Raspaud A (2012) Generalized power domination of graphs. Discrete Appl Math 160(12):1691–1698MathSciNetCrossRefMATH

Chang GJ, Roussel N (2015) On the $k$-power domination of hypergraphs. J Comb Optim 30(4):1095–1106MathSciNetCrossRefMATH

Desormeaux WJ, Haynes TW, Henning MA (2013) Bounds on the connected domination number of a graph. Discrete Appl Math 161(18):2925–2931MathSciNetCrossRefMATH

Desrochers M, Laporte G (1991) Improvements and extensions to the Miller–Tucker–Zemlin subtour elimination constraints. Oper Res Lett 10(1):27–36MathSciNetCrossRefMATH

Dilkina BN, Gomes CP (2010) Solving connected subgraph problems in wildlife conservation. In: CPAIOR, vol 6140. Springer, pp 102–116

Dorbec P, Klavžar S (2014) Generalized power domination: propagation radius and Sierpiński graphs. Acta Appl Math 134(1):75–86MathSciNetCrossRefMATH

Edholm CJ, Hogben L, LaGrange J, Row DD (2012) Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph. Linear Algebra Appl 436(12):4352–4372MathSciNetCrossRefMATH

Fan N, Watson J-P (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. In: International conference on combinatorial optimization and applications. Springer, pp 371–383

Ferrero D, Hogben L, Kenter FH, Young M (2017) Note on power propagation time and lower bounds for the power domination number. J Comb Optim 34(3):736–741MathSciNetCrossRefMATH

Fomin FV, Grandoni F, Kratsch D (2008) Solving connected dominating set faster than $2^n$. Algorithmica 52(2):153–166MathSciNetCrossRefMATH

Garey MR, Johnson DS (1979) Computers and intractability. W.H. Freeman & Co., San FranciscoMATH

Guo J, Niedermeier R, Raible D (2005) Improved algorithms and complexity results for power domination in graphs. In: FCT, vol 3623. Springer, pp 172–184

Haynes TW, Hedetniemi SM, Hedetniemi ST, Henning MA (2002) Domination in graphs applied to electric power networks. SIAM J Discrete Math 15(4):519–529MathSciNetCrossRefMATH

Huang L-H, Chang GJ, Yeh H-G (2010) On minimum rank and zero forcing sets of a graph. Linear Algebra Appl 432(11):2961–2973MathSciNetCrossRefMATH

Huang L, Sun Y, Xu J, Gao W, Zhang J, Wu Z (2014) Optimal PMU placement considering controlled islanding of power system. IEEE Trans Power Syst 29(2):742–755CrossRef

IEEE reliability test data (2012). http://www.ee.washington.edu/research/pstca/

Kneis J, Mölle D, Richter S, Rossmanith P (2006) Parameterized power domination complexity. Inf Process Lett 98(4):145–149MathSciNetCrossRefMATH

Li Q, Cui T, Weng Y, Negi R, Franchetti F, Ilic MD (2013) An information-theoretic approach to PMU placement in electric power systems. IEEE Trans Smart Grid 4(1):446–456CrossRef

Li Y, Yang Z, Wang W (2017) Complexity and algorithms for the connected vertex cover problem in 4-regular graphs. Appl Math Comput 301:107–114MathSciNetMATH

Liao C-S (2016) Power domination with bounded time constraints. J Comb Optim 31(2):725–742MathSciNetCrossRefMATH

Liao C-S, Lee D-T (2005) Power domination problem in graphs. In: COCOON. Springer, pp 818–828

Manousakis NM, Korres GN, Georgilakis PS (2012) Taxonomy of PMU placement methodologies. IEEE Trans Power Syst 27(2):1070–1077CrossRef

Martin RK (1991) Using separation algorithms to generate mixed integer model reformulations. Oper Res Lett 10(3):119–128MathSciNetCrossRefMATH

Mili L, Baldwin T, Phadke A (1991) Phasor measurements for voltage and transient stability monitoring and control. In: Workshop on application of advanced mathematics to power systems, San Francisco

Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7(4):326–329MathSciNetCrossRefMATH

Nylen PM (1996) Minimum-rank matrices with prescribed graph. Linear Algebra Appl 248:303–316MathSciNetCrossRefMATH

Peng J, Sun Y, Wang H (2006) Optimal PMU placement for full network observability using Tabu search algorithm. Int J Electr Power Energy Syst 28(4):223–231CrossRef

Quintão FP, da Cunha AS, Mateus GR, Lucena A (2010) The k-cardinality tree problem: reformulations and Lagrangian relaxation. Discrete Appl Math 158(12):1305–1314MathSciNetCrossRefMATH

Row D (2012) Zero forcing number, path cover number, and maximum nullity of cacti. Involve 4(3):277–291MathSciNetCrossRefMATH

Sampathkumar E, Walikar HB (1979) The connected domination number of a graph. J Math Phys Sci 13(6):607–613MathSciNetMATH

Sodhi R, Srivastava S, Singh S (2011) Multi-criteria decision-making approach for multi-stage optimal placement of phasor measurement units. IET Gener Transm Distrib 5(2):181–190CrossRef

Tarjan RE (1974) A note on finding the bridges of a graph. Inf Process Lett 2(6):160–161MathSciNetCrossRefMATH

Yang B (2013) Fast-mixed searching and related problems on graphs. Theor Comput Sci 507:100–113MathSciNetCrossRefMATH

Titel: Connected power domination in graphs
verfasst von: Boris Brimkov
Derek Mikesell
Logan Smith
Publikationsdatum: 23.01.2019
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 1/2019
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00380-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2019

Model and algorithm of routes planning for emergency relief distribution in disaster management with disaster information update

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem

On the randomized online strategies for the k-Canadian traveler problem

Determining the interset distance

Optimal channel assignment with list-edge coloring

Non-adaptive group testing on graphs with connectivity