Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tree decomposition:
TR00-064 | 29th August 2000
Klaus Jansen, Marek Karpinski, Andrzej Lingas

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

The Max-Bisection and Min-Bisection are the problems of finding
partitions of the vertices of a given graph into two equal size subsets so as
to maximize or minimize, respectively, the number of edges with exactly one
endpoint in each subset.
In this paper we design the first ... more >>>

TR01-023 | 13th March 2001
Jochen Alber, Henning Fernau, Rolf Niedermeier

Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint