English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  The Curse of Connectivity: t-Total Vertex (Edge) Cover

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC0B-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC0C-9
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Fernau, Henning1, Author
Fomin, Fedor V.1, Author
Philip, Geevarghese1, Author           
Saurabh, Saket1, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: 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

Details

show
hide
Language(s): eng - English
 Dates: 20102010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-14031-0
BibTex Citekey: FernauFominPhilipSaurabh2010
 Degree: -

Event

show
hide
Title: COCOON 2010
Place of Event: Nha Trang, Vietnam
Start-/End Date: 2010-07-19 - 2010-07-21

Legal Case

show

Project information

show

Source 1

show
hide
Title: Computing and Combinatorics
  Abbreviation : COCOON 2010
  Subtitle : 6th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings
Source Genre: Proceedings
 Creator(s):
Thai, My T.1, Editor
Sahni, Sartaj1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 34 - 43 Identifier: ISBN: 978-3-642-14030-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 6196 Sequence Number: - Start / End Page: - Identifier: -