An exact algorithm for connected red–blue dominating set
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 proble...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | article |
| منشور في: |
2011
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/2776 http://dx.doi.org/10.1016/j.jda.2011.03.006 http://www.sciencedirect.com/science/article/pii/S1570866711000360 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513459371114496 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Mouawad, Amer E. Liedloff, Mathieu |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Mouawad, Amer E. Liedloff, Mathieu |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Mouawad, Amer E. Liedloff, Mathieu |
| dc.date.none.fl_str_mv | 2011 2015-12-07T12:26:57Z 2015-12-07T12:26:57Z 2015-12-07 |
| dc.identifier.none.fl_str_mv | 1570-8667 http://hdl.handle.net/10725/2776 http://dx.doi.org/10.1016/j.jda.2011.03.006 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. http://www.sciencedirect.com/science/article/pii/S1570866711000360 http://www.sciencedirect.com/science/article/pii/S1570866711000360 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Journal of Discrete Algorithms |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | An exact algorithm for connected red–blue dominating set |
| dc.type.none.fl_str_mv | Article info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | 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). |
| eu_rights_str_mv | openAccess |
| format | article |
| id | LAURepo_6fcdd143ca0052f91e5225da5bb78ed2 |
| identifier_str_mv | 1570-8667 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/2776 |
| publishDate | 2011 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | An exact algorithm for connected red–blue dominating setAbu-Khzam, Faisal N.Mouawad, Amer E.Liedloff, MathieuIn 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).PublishedN/A2015-12-07T12:26:57Z2015-12-07T12:26:57Z20112015-12-07Articleinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/article1570-8667http://hdl.handle.net/10725/2776http://dx.doi.org/10.1016/j.jda.2011.03.006Abu-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.http://www.sciencedirect.com/science/article/pii/S1570866711000360http://www.sciencedirect.com/science/article/pii/S1570866711000360enJournal of Discrete Algorithmsinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/27762016-08-26T10:06:19Z |
| spellingShingle | An exact algorithm for connected red–blue dominating set Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | An exact algorithm for connected red–blue dominating set |
| title_full | An exact algorithm for connected red–blue dominating set |
| title_fullStr | An exact algorithm for connected red–blue dominating set |
| title_full_unstemmed | An exact algorithm for connected red–blue dominating set |
| title_short | An exact algorithm for connected red–blue dominating set |
| title_sort | An exact algorithm for connected red–blue dominating set |
| url | http://hdl.handle.net/10725/2776 http://dx.doi.org/10.1016/j.jda.2011.03.006 http://www.sciencedirect.com/science/article/pii/S1570866711000360 |