.

An improved kernel for the undirected planar feedback vertex set problem

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Bou Khuzam, Mazen
dc.date.accessioned 2017-03-17T12:32:03Z
dc.date.available 2017-03-17T12:32:03Z
dc.identifier.isbn 978-3-642-33293-7 en_US
dc.identifier.uri http://hdl.handle.net/10725/5379
dc.description.abstract We consider the parameterized Feedback Vertex Set problem on unweighted, undirected planar graphs. We present a kernelization algorithm that takes a planar graph G and an integer k as input and either decides that (G,k) is a no instance or produces an equivalent (kernel) instance (G′,k′) such that k′ ≤ k and |V(G′)| < 97k. In addition to the improved kernel bound (from 112k to 97k), our algorithm features simple linear-time reduction procedures that can be applied to the general Feedback Vertex Set problem. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title An improved kernel for the undirected planar feedback vertex set problem en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-642-33293-7_25 en_US
dc.identifier.ctation Abu-Khzam, F. N., & Khuzam, M. B. (2012, September). An improved kernel for the undirected planar feedback vertex set problem. In International Symposium on Parameterized and Exact Computation (pp. 264-273). Springer Berlin Heidelberg. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date September 12-14, 2012 en_US
dc.conference.pages 264-273 en_US
dc.conference.place Ljubljana, Slovenia en_US
dc.conference.title International Symposium on Parameterized and Exact Computation en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/978-3-642-33293-7_25 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Parameterized and Exact Computation en_US


Files in this item

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR


Advanced Search

Browse

My Account