All reports by Author Rohit Khandekar:

__
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

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

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