|Publisher DOI:||10.1007/978-3-662-44777-2_29||Title:||Large independent sets in triangle-free planar graphs||Language:||English||Authors:||Dvořák, Zdeněk
|Issue Date:||2014||Source:||22nd Annual European Symposium on Algorithms (ESA 2014)||Part of Series:||Lecture notes in computer science||Journal or Series Name:||Lecture notes in computer science||Abstract (english):||
Every triangle-free planar graph on n vertices has an independent set of size at least (n+1)/3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k≥0, decides whether G has an independent set of size at least (n+k)/3, in time 20(√k). Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists ε>0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3-ε).
|Conference:||22nd Annual European Symposium on Algorithms (ESA 2014)||URI:||http://hdl.handle.net/11420/7627||ISBN:||978-366244776-5||ISSN:||0302-9743||Document Type:||Chapter/Article (Proceedings)|
|Appears in Collections:||Publications without fulltext|
Show full item record
checked on Jan 17, 2021
Add Files to Item
Note about this record
Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.