RAIRO-Theor. Inf. Appl.
Volume 48, Number 5, December 2014
|Page(s)||541 - 549|
|Published online||12 January 2015|
Domination problems on P5-free graphs∗
Accepted: 15 September 2014
The minimum roman dominating problem (denoted by γR(G), the weight of minimum roman dominating function of graph G) is a variant of the very well known minimum dominating set problem (denoted by γ(G), the cardinality of minimum dominating set of graph G). Both problems remain NP-Complete when restricted to P5-free graph class [A.A. Bertossi, Inf. Process. Lett. 19 (1984) 37–40; E.J. Cockayne, et al. Discret. Math. 278 (2004) 11–22]. In this paper we study both problems restricted to some subclasses of P5-free graphs. We describe robust algorithms that solve both problems restricted to (P5,(s,t)-net)-free graphs in polynomial time. This result generalizes previous works for both problems, and improves existing algorithms when restricted to certain families such as (P5,bull)-free graphs. It turns out that the same approach also serves to solve problems for general graphs in polynomial time whenever γ(G) and γR(G) are fixed (more efficiently than naive algorithms). Moreover, the algorithms described are extremely simple which makes them useful for practical purposes, and as we show in the last section it allows to simplify algorithms for significant classes such as cographs.
Mathematics Subject Classification: 05C69 / 05C85
Key words: Algorithms / dominating set / roman dominating function / P5-free graphs
© EDP Sciences 2015
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.