Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Separator:
TR05-013 | 22nd December 2004
Bin Fu

Theory and Application of Width Bounded Geometric Separator

We introduce the notion of width bounded geometric separator,
develop the techniques for its existence as well as algorithm, and
apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the
disk covering problem, which seeks to determine the minimal number
of fixed size disks to cover $n$ points on ... more >>>

TR19-181 | 9th December 2019
Michal Koucky, Vojtech Rodl, Navid Talebanfard

A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. ... more >>>

ISSN 1433-8092 | Imprint