10 citations · 26 across the 5 of their papers we have counts for
3 papers · 1 filter
Finding large induced sparse subgraphs in -free graphs in quasipolynomial time
Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk +2
For an integer , a graph is called {\em{-free}} if does not contain any induced cycle on more than~ vertices. We prove the following statement: for every pair…
A O(c^k n) 5-Approximation Algorithm for Treewidth
Hans Bodlaender, Pål G. Drange, Markus S. Dregi +3
We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of…
Designing FPT algorithms for cut problems using randomized contractions
Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi +2
We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. We apply our framework to obtain the first FPT algorithm for…