Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with UGC:
TR16-112 | 18th July 2016
Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

Bicovering: Covering edges with two small subsets of vertices

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

ISSN 1433-8092 | Imprint