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

アイテム詳細

登録内容を編集ファイル形式で保存
 
 
ダウンロード電子メール
 タグ情報を表示リリース履歴を表示詳細要約
  A Single-exponential FPT Algorithm for the K4-Minor Cover Problem

Kim, E. J., Paul, C., & Philip, G. (2012). A Single-exponential FPT Algorithm for the K4-Minor Cover Problem. In F. V., Fomin, & P., Kaski (Eds.), Algorithm Theory - SWAT 2012 (pp. 119-130). Berlin: Springer.

Item is

 

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

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0014-BDEF-A 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0023-C080-B
資料種別: 会議論文
LaTeX : A Single-exponential {FPT} Algorithm for the {K4-Minor} Cover Problem

ファイル

表示: ファイル
非表示: ファイル
:
swat-lncs.pdf (全文テキスト（全般）), 336KB
 
ファイルのパーマリンク:
-
ファイル名:
swat-lncs.pdf
説明:
-
OA-Status:
閲覧制限:
非公開
MIMEタイプ / チェックサム:
application/pdf
技術的なメタデータ:
著作権日付:
-
著作権情報:
-
CCライセンス:
-

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Kim, Eun Jung1, 著者
Paul, Christophe1, 著者
Philip, Geevarghese2, 著者           
所属:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

内容説明

表示:
非表示:
キーワード: -
 要旨: Given an input graph G on \(n\) vertices and an integer k, the parameterized \textscK_4-minor cover} problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called \textsc{Treewidth-2 Vertex Deletion}. This problem is inspired by two well-studied parameterized vertex deletion problems, \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}, which can be expressed as \textsc{Treewidth-t Vertex Deletion} problems: t=0 for {\sc Vertex Cover} and t=1 for {\sc Feedback Vertex Set}. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for \textsc{Feedback Vertex Set} was devised comparatively recently. While it is known to be unlikely that \textsc{Treewidth-t Vertex Deletion} can be solved in time c^{o(k)}⋅ n^{O(1)}, it was open whether the \textsc{K_4-minor cover} could be solved in single-exponential FPT time, i.e. in c^k⋅ n^{O(1) time. This paper answers this question in the affirmative.

資料詳細

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

関連イベント

表示:
非表示:
イベント名: 13th Scandinavian Symposium and Workshops on Algorithm Theory
開催地: Helsinki, Finland
開始日・終了日: 2012-07-04 - 2012-07-06

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Algorithm Theory - SWAT 2012
  副タイトル : 13th Scandinavian Symposium and Workshops
  省略形 : SWAT 2012
種別: 会議論文集
 著者・編者:
Fomin, Fedor V.1, 編集者
Kaski, Petteri1, 編集者
所属:
1 External Organizations, ou_persistent22            
出版社, 出版地: Berlin : Springer
ページ: - 巻号: - 通巻号: - 開始・終了ページ: 119 - 130 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-3-642-31154-3

出版物 2

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