The planar connected face-dominating set problem. (c2015)

LAUR Repository

Show simple item record

dc.contributor.author Hage-Ali, Dina Y.
dc.date.accessioned 2015-04-16T06:56:45Z
dc.date.available 2015-04-16T06:56:45Z
dc.date.issued 2016-01-28
dc.date.submitted 2015-01-20
dc.identifier.uri http://hdl.handle.net/10725/1991
dc.description Includes bibliographical references (leaves 39-40). en_US
dc.description.abstract In the Planar Connected Face-Dominating Set problem, we are given a plane graph G and asked to find a connected subgraph T of minimum weight, or order, such that the boundary of every face of G contains at least one element of T. This problem can be reduced to the planar connected red-blue dominating set problem, which is a recently studied version of the Steiner Tree problem. We study the complexity of Planar Connected Face-Dominating Set with respect to various parameterizations and present some heuristics that make use of the degree structure of real data. Inparticular, we introduce and study a greedy heuristic that is based on high-degree vertices and minimum-spanning trees. Experiments show that our approach is efficient and delivers results that are close to optimum. en_US
dc.language.iso en en_US
dc.subject Graph theory en_US
dc.subject Domination (Graph theory) en_US
dc.subject Steiner systems en_US
dc.subject Lebanese American University -- Dissertations en_US
dc.subject Dissertations, Academic en_US
dc.title The planar connected face-dominating set problem. (c2015) en_US
dc.type Thesis en_US
dc.term.submitted Fall en_US
dc.author.degree MS in Computer Science en_US
dc.author.school Arts and Sciences en_US
dc.author.idnumber 200103079 en_US
dc.author.commembers Dr. Nashat Mansour
dc.author.commembers Dr. Samer Habre
dc.author.woa OA en_US
dc.description.physdesc 1 hard copy: x, 40 leaves; ill.; 31 cm. available at RNL. en_US
dc.author.division Computer Science en_US
dc.author.advisor Dr. Faisal Abu Khzam
dc.keywords Plane Graph en_US
dc.keywords Subgraph en_US
dc.keywords Face Cover en_US
dc.keywords Steiner Tree en_US
dc.keywords Connected Red-Blue Dominating Set en_US
dc.identifier.doi https://doi.org/10.26756/th.2015.4 en_US
dc.publisher.institution Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account