Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Journal of Combinatorial Optimization
Erschienen in: Journal of Combinatorial Optimization 2/2016

01.02.2016

\(k\)-Power domination in block graphs

verfasst von: Chao Wang, Lei Chen, Changhong Lu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2016

Einloggen

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

search-config
loading …

Abstract

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.
Vorheriger Artikel An approximation algorithm for the partial vertex cover problem in hypergraphs
Nächster Artikel Adjacent vertex-distinguishing edge coloring of 2-degenerate graphs

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
Literatur
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–1399MathSciNetCrossRefMATH
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
Chen L, Lu C, Zeng Z (2010) Labelling algorithms for paired-domination problems in block and interval graphs. J Comb Optim 19:457–470MathSciNetCrossRefMATH
Chen L, Lu C, Zeng Z (2009) A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inf Process Lett 110:20–23MathSciNetCrossRefMATH
Cockayne EJ, Goodman SE, Hedetniemi ST (1975) A linear algorithm for the domination number of a tree. Inf Process Lett 4:41–44CrossRefMATH
Dorbec P, Henning MA, Lowenstein C, Montassier M, Raspaud A (2013) Generalized power domination in regular graphs. SIAM J Discret Math 27:1559–1574MathSciNetCrossRefMATH
Dorbec P, Mollard M, Klavžar S, Špacapan S (2008) Power domination in product graphs. SIAM J Discret Math 22:554–567CrossRefMATH
Guo J, Niedermeier R, Raible D (2008) Improved algorithms and complexity results for power domination in graphs. Algorithmica 52:177–202MathSciNetCrossRefMATH
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–529MathSciNetCrossRefMATH
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
Wimer TV (1987) Linear algorithms on \(k\)-terminal graphs, Ph.D. Thesis, Clemson University
Yen WCK (2003) The bottleneck independent domination on the classes of bipartite graphs and block graphs. Inf Sci 157:199–215CrossRefMATH
Metadaten
Titel
-Power domination in block graphs
verfasst von
Chao Wang
Lei Chen
Changhong Lu
Publikationsdatum
01.02.2016
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2016
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-014-9795-0

Weitere Artikel der Ausgabe 2/2016

Journal of Combinatorial Optimization 2/2016 Zur Ausgabe

OriginalPaper

-labeling for brick product graphs

OriginalPaper

A sufficient condition for a tree to be --totally labelable

OriginalPaper

Degree conditions for weakly geodesic pancyclic graphs and their exceptions

OriginalPaper

Degree-constrained orientations of embedded graphs

OriginalPaper

Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis

OriginalPaper

On single machine scheduling with resource constraint

Premium Partner

    Bildnachweise