Now showing items 1-2 of 2

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

(Master thesis, 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 ...
• #### Kernelization of Vertex Cover by Structural Parameters ﻿

(Master thesis, 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 ...