All reports by Author Rolf Niedermeier:

__
TR01-023
| 13th March 2001
__

Jochen Alber, Henning Fernau, Rolf Niedermeier#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

__
TR00-037
| 26th May 2000
__

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith#### New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

Jochen Alber, Henning Fernau, Rolf Niedermeier

A parameterized problem is called fixed parameter tractable

if it admits a solving algorithm whose running time on

input instance $(I,k)$ is $f(k) \cdot |I|^\alpha$, where $f$

is an arbitrary function depending only on~$k$. Typically,

$f$ is some exponential function, e.g., $f(k)=c^k$ for ...
more >>>

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

The maximum 2-satisfiability problem (MAX-2-SAT) is:

given a Boolean formula in $2$-CNF, find a truth

assignment that satisfies the maximum possible number

of its clauses. MAX-2-SAT is MAXSNP-complete.

Recently, this problem received much attention in the

contexts of approximation (polynomial-time) algorithms

...
more >>>