An improved kernel for the undirected planar feedback vertex set problem

Abu-Khzam, Faisal N.; Bou Khuzam, Mazen

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.date.issued	2017-03-17
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