## Search

Now showing items 1-2 of 2

#### Exact algorithms for MAX-2SAT and MAX-3SAT via multidimensional matrix multiplication

(The University of Bergen, 2015-06-01)

In this thesis it is showed how an $O(n^{4-\epsilon})$ algorithm for the cube multiplication problem (that is defined in the thesis) would imply a faster than naive $O^{*}(2^{n(1-\frac{\epsilon}{4})})$ algorithm for the ...

#### Kernelization of Vertex Cover by Structural Parameters

(The University of Bergen, 2015-08-03)

In the NP-complete problem Vertex Cover, one is given a graph G and an integer k and are asked whether there exists a vertex set S ⊆ V (G) with size at most k such that every edge of the graph is incident to a vertex in ...