Andreas Björklund

activity

20062026

most citedThe fast intersection transform with applications to counting paths

14 citations · 32 across the 19 of their papers we have counts for

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.DS2015

Fast Witness Extraction Using a Decision Oracle

Andreas Björklund, Petteri Kaski, Łukasz Kowalik

The gist of many (NP-)hard combinatorial problems is to decide whether a universe of $n$ elements contains a witness consisting of $k$ elements that match some prescribed pattern.…

cs.DS2015

Coloring Graphs having Few Colorings over Path Decompositions

Andreas Björklund

Lokshtanov, Marx, and Saurabh SODA 2011 proved that there is no $(k - ε)^{pw (G)} poly (n)$ time algorithm for deciding if an $n$ -vertex graph $G$ with pat…

cs.DS2015

Spotting Trees with Few Leaves

Andreas Björklund, Vikram Kamat, Łukasz Kowalik +1

We show two results related to the Hamiltonicity and $k$ -Path algorithms in undirected graphs by Björklund [FOCS'10], and Björklund et al., [arXiv'10]. First, we demonstrate that t…