Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with problem kernel:
TR04-078 | 3rd August 2004
Henning Fernau

Two-Layer Planarization: Improving on Parameterized Algorithmics

A bipartite graph is biplanar if the vertices can be
placed on two parallel lines in the plane such that there are
no edge crossings when edges are drawn as straight-line segments.
We study two variants of biplanarization problems:
- Two-Layer Planarization TLP: can $k$ edges be deleted from
a ... more >>>

TR08-066 | 16th July 2008
Noga Alon, Shai Gutner

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

The domination number of a graph $G=(V,E)$ is the minimum size of
a dominating set $U \subseteq V$, which satisfies that every
vertex in $V \setminus U$ is adjacent to at least one vertex in
$U$. The notion of a problem kernel refers to a polynomial time
algorithm that achieves ... more >>>

ISSN 1433-8092 | Imprint