Fernau, Henning ; Fomin, Fedor V. ; Philip, Geevarghese ; Saurabh, Saket (2010) The Curse of Connectivity: t-Total Vertex (Edge) Cover In: 16th Annual International Conference, COCOON 2010, July 19-21, 2010, Nha Trang, Vietnam.
Full text not available from this repository.
Official URL: https://www.springerprofessional.de/en/computing-a...
Abstract
We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely k-Vertex Cover and k-Edge Cover. Specifically, we impose the additional requirement that each connected component of a solution have at least t vertices (resp. edges from the solution), and call the problem t-total vertex cover (resp. t-total edge cover).
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| ID Code: | 123426 |
| Deposited On: | 16 Sep 2021 10:43 |
| Last Modified: | 16 Sep 2021 10:43 |
Repository Staff Only: item control page
