An exact algorithm for connected red–blue dominating set

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Mouawad, Amer E.
dc.contributor.author Liedloff, Mathieu
dc.date.accessioned 2015-12-07T12:26:57Z
dc.date.available 2015-12-07T12:26:57Z
dc.date.copyright 2011
dc.date.issued 2015-12-07
dc.identifier.issn 1570-8667 en_US
dc.identifier.uri http://hdl.handle.net/10725/2776
dc.description.abstract In the Connected Red–Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of G is adjacent to some vertex in S . The problem can be solved in O⁎(2n−|B|) time by reduction to the Weighted Steiner Tree problem. Combining exhaustive enumeration when |B| is small with the Weighted Steiner Tree approach when |B| is large, solves the problem in O⁎(n1.4143). In this paper we present a first non-trivial exact algorithm whose running time is in O⁎(n1.3645). We use our algorithm to solve the Connected Dominating Set problem in O⁎(n1.8619). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O⁎(n1.8966). en_US
dc.language.iso en en_US
dc.title An exact algorithm for connected red–blue dominating set en_US
dc.type Article en_US
dc.description.version Published en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.woa N/A en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.relation.journal Journal of Discrete Algorithms en_US
dc.journal.volume 9 en_US
dc.journal.issue 3 en_US
dc.article.pages 252-262 en_US
dc.keywords Exact algorithm en_US
dc.keywords Dominating set en_US
dc.keywords Weighted Steiner tree en_US
dc.identifier.doi http://dx.doi.org/10.1016/j.jda.2011.03.006 en_US
dc.identifier.ctation Abu-Khzam, F. N., Mouawad, A. E., & Liedloff, M. (2011). An exact algorithm for connected red–blue dominating set. Journal of Discrete Algorithms, 9(3), 252-262. en_US
dc.author.email faisal.abukhzam@lau.edu.lb
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S1570866711000360
dc.identifier.url http://www.sciencedirect.com/science/article/pii/S1570866711000360

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account