All reports by Author Andreas Björklund:

__
TR06-044
| 24th January 2006
__

Andreas Björklund, Thore Husfeldt#### Inclusion-Exclusion Based Algorithms for Graph Colouring

__
TR03-032
| 16th April 2003
__

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna#### Approximating Longest Directed Path

Andreas Björklund, Thore Husfeldt

We present a deterministic algorithm producing the number of

$k$-colourings of a graph on $n$ vertices in time

$2^nn^{O(1)}$.

We also show that the chromatic number can be found by a

polynomial space algorithm running in time $O(2.2461^n)$.

Finally, we present a family of ...
more >>>

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

We investigate the hardness of approximating the longest path and

the longest cycle in directed graphs on $n$ vertices. We show that

neither of these two problems can be polynomial time approximated

within $n^{1-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

more >>>