Top

Journal of Combinatorial Optimization

Published in:

24-10-2019

Approximation algorithm for a generalized Roman domination problem in unit ball graphs

Authors: Limin Wang, Yalin Shi, Zhao Zhang, Zan-Bo Zhang, Xiaoyan Zhang

Published in: Journal of Combinatorial Optimization | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we propose a generalized Roman domination problem called connected strong k-Roman dominating set problem. It is NP-hard even in a unit ball graph. Unit ball graphs are the intersection graphs of equal sized balls in the three-dimensional space, they are widely used as a mathematical model for wireless sensor networks and some problems in computational geometry. This paper presents the first constant approximation algorithm with a guaranteed performance ratio at most \(6(k+2)\) in unit ball graphs, where k is a positive integer.

previous article On the extremal graphs with respect to the total reciprocal edge-eccentricity

next article Remarks on Barnette’s conjecture

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Akyildiz IF, Pompili D, Melodia T (2005) Underwater acoustic sensor networks: research challenges. Ad Hoc Netw 3:257–279CrossRef

Cockayne EJ, Dreyer PA Jr, Hedetniemi SM, Hedetniemi ST (2004) Roman domination in graphs. Discrete Math 278(1–3):11–22MathSciNetCrossRef

Chambers EW, Kinnersley B, Prince N, West DB (2009) Extremal problem for Roman domination. SIAM J Discrete Math 23(3):1575–1586MathSciNetCrossRef

Dreyer PA Jr (2000) Applications and variations of domination in graphs. Rutgers University, New Jersey PhD Thesis

Henning MA (2003) Defending the roman empire from multiple attacks. Discrete Math 271(1–3):101–115MathSciNetCrossRef

Henning MA, Hedetniemi ST (2003) Defending the Roman empire—a new strategy. Discrete Math 266:239–251MathSciNetCrossRef

Huang H, Richa AW, Segal M (2004) Approximation algorithms for the mobile piercing set problem with applications to clustering in ad hoc networks. Mob Netw Appl 9(2):151–161CrossRef

Lideloff M, Kloks T, Liu J, Peng SL (2005) Roman domination over some graph classes. In: Kratsch D (ed) WG 2005. LNCS 3787, pp 103–114

Liu CH, Chang GJ (2012) Roman domination on 2-connected graphs. SIAM J Discrete Math 26(1):193–205MathSciNetCrossRef

Pagourtzis A, Penna P, Schlude K, Steinhofel K, Taylor DS, Widmayer P (2002) Server placements, Roman domination and other dominating set variants. Found Inf Technol Era Netw Mob Comput 96:280–291CrossRef

Shang WP, Hu XD (2007) The Roman domination problem in unit disk graphs. In: Shi Y et al (eds) ICCS 2007. Part III, LNCS 4489, pp 305–312CrossRef

Shang WP, Wang XM, Hu XD (2010) Roman domination and the variants in unit disk graphs. Discrete Math Algorithms Appl 2(1):99–105MathSciNetCrossRef

Stewart I (1999) Defend the Roman empire!. Sci Am 281(6):136–138CrossRef

Zhu EQ, Shao ZH (2018) Extremal problems on weak Roman domination number. Inf Process Lett 138:12–18MathSciNetCrossRef

Title: Approximation algorithm for a generalized Roman domination problem in unit ball graphs
Authors: Limin Wang
Yalin Shi
Zhao Zhang
Zan-Bo Zhang
Xiaoyan Zhang
Publication date: 24-10-2019
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-019-00459-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Algorithmic results on double Roman domination in graphs

Approximation algorithms for two-stage flexible flow shop scheduling

The structure of graphs with given number of blocks and the maximum Wiener index

Bounds on upper transversals in hypergraphs

Neighbor sum distinguishing total colorings of IC-planar graphs with maximum degree 13

Less is more approach for competing groups scheduling with different learning effects

Premium Partner