Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Planar graph problems:
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 >>>

TR19-039 | 12th March 2019
Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

Planarity, Exclusivity, and Unambiguity

Comments: 1

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

ISSN 1433-8092 | Imprint