Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

The Curse of Connectivity: t-Total Vertex (Edge) Cover

MPG-Autoren
Es sind keine MPG-Autoren in der Publikation vorhanden
Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Fernau, H., Fomin, F. V., Philip, G., & Saurabh, S. (2010). The Curse of Connectivity: t-Total Vertex (Edge) Cover. In M. T. Thai, & S. Sahni (Eds.), Computing and Combinatorics (pp. 34-43). Berlin: Springer. doi:10.1007/978-3-642-14031-0.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0019-DC0B-B
Zusammenfassung
We investigate the effect of certain natural connectivity constraints on the parameterized complexity of two fundamental graph covering problems, namely Vertex Cover and 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). We show that \beginitemize} \item both problems remain fixed-parameter tractable with these restrictions, with running times of the form \Oh^{*}≤ft(c^{k}\right) for some constant c>0 in each case; \item for every t≥2,t-Total Vertex Cover has no polynomial kernel unless the Polynomial Hierarchy collapses to the third level; \item for every t≥2, t-Total Edge Cover has a linear vertex kernel of size \frac{t+1}{t}k. \end{itemize