日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
一時保存へ追加
 タグ情報を表示リリース履歴を表示詳細要約
  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

 

表示: 全項目 非表示: 全項目

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0019-DC0B-B 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0019-DC0C-9
資料種別: 会議論文

ファイル

表示: ファイル

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Fernau, Henning1, 著者
Fomin, Fedor V.1, 著者
Philip, Geevarghese1, 著者           
Saurabh, Saket1, 著者
所属:
1External Organizations, ou_persistent22              

内容説明

表示:
非表示:
キーワード: -
 要旨: 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

資料詳細

表示:
非表示:
言語: eng - English
 日付: 20102010
 出版の状態: 出版
 ページ: -
 出版情報: -
 目次: -
 査読: -
 識別子（DOI, ISBNなど）: DOI: 10.1007/978-3-642-14031-0
BibTex参照ID: FernauFominPhilipSaurabh2010
 学位: -

関連イベント

表示:
非表示:
イベント名: COCOON 2010
開催地: Nha Trang, Vietnam
開始日・終了日: 2010-07-19 - 2010-07-21

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Computing and Combinatorics
  省略形 : COCOON 2010
  副タイトル : 6th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings
種別: 会議論文集
 著者・編者:
Thai, My T.1, 編集者
Sahni, Sartaj1, 編集者
所属:
1 External Organizations, ou_persistent22            
出版社, 出版地: Berlin : Springer
ページ: - 巻号: - 通巻号: - 開始・終了ページ: 34 - 43 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-3-642-14030-3

出版物 2

表示:
非表示:
出版物名: Lecture Notes in Computer Science
  省略形 : LNCS
種別: 連載記事
 著者・編者:
所属:
出版社, 出版地: -
ページ: - 巻号: 6196 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -