Exact Algorithms for Weak Roman Domination

Abstract : We consider the Weak Roman Domination problem. Given an undirected graph G = (V,E), the aim is to find a weak roman domination function (wrd-function for short) of minimum cost, i.e. a function f: V → {0,1,2} such that every vertex v ∈ V is defended (i.e. there exists a neighbor u of v, possibly u = v, such that f(u)≥1) and for every vertex v ∈ V with f(v) = 0 there exists a neighbor u of v such that f(u)≥1 and the function fu → v defined by:fu→v(x)={1 if x=v,f(u)-1 if x=u,f(x) if x∉{u,v}} does not contain any undefended vertex. The cost of a wrd-function f is defined by cost(f) = ∑  v ∈ V f(v). The trivial enumeration algorithm runs in time O(3n) and polynomial space and is the best one known for the problem so far. We are breaking the trivial enumeration barrier by providing two faster algorithms: we first prove that the problem can be solved in O(2n) time needing exponential space, and then describe an O(2.2279n) algorithm using polynomial space. Our results rely on structural properties of a wrd-function, as well as on the best polynomial space algorithm for the Red-Blue Dominating Set problem.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00848454
Contributor : Mathieu Chapelle <>
Submitted on : Friday, July 26, 2013 - 10:39:57 AM
Last modification on : Thursday, January 17, 2019 - 3:06:04 PM

Links full text

Identifiers

Citation

Mathieu Chapelle, Manfred Cochefert, Jean-François Couturier, Dieter Kratsch, Mathieu Liedloff, et al.. Exact Algorithms for Weak Roman Domination. IWOCA 2013, Jul 2013, Rouen, France. pp.81-93, ⟨10.1007/978-3-642-45278-9_8⟩. ⟨hal-00848454⟩

Share

Metrics

Record views

385