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

アイテム詳細

登録内容を編集ファイル形式で保存
一時保存へ追加
 タグ情報を表示リリース履歴を表示詳細要約
  Ranking and Drawing in Subexponential Time

Fernau, H., Fomin, F. V., Lokshtanov, D., Mnich, M., Philip, G., & Saurabh, S. (2011). Ranking and Drawing in Subexponential Time. In C. S., Iliopoulos, & W., F. Smyth (Eds.), Combinatorial Algorithms. Berlin: Springer. doi:10.1007/978-3-642-19222-7_34.

Item is

 

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

基本情報

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

ファイル

表示: ファイル

関連URL

表示:

作成者

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

内容説明

表示:
非表示:
キーワード: -
 要旨: In this paper we obtain parameterized subexponential-time algorithms for \kaggLG{} (\kagg{}) --- a problem in social choice theory --- and for \oscmLG{} (\oscm{}) -- a problem in graph drawing (see the introduction for definitions). These algorithms run in time \Oh^*}(2^{\Oh(\sqrt{k}\log k)}), where k is the parameter, and significantly improve the previous best algorithms with running times \Oh^{*}(1.403^k) and \Oh^{*}(1.4656^k), respectively. We also study natural ``above-guarantee'' versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of {\sc p-Directed Feedback Arc Set}. Our results for the above-guarantee version of \kagg{} reveal an interesting contrast. We show that when the number of ``votes'' in the input to \kagg{} is {\em odd} the above guarantee version can still be solved in time O^{*}(2^{\Oh(\sqrt{k}\log k)}), while if it is {\em even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails (equivalently, unless FPT=M[1]).

資料詳細

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

関連イベント

表示:
非表示:
イベント名: IWOCA 2010
開催地: London, United Kingdom
開始日・終了日: 2010-07-26 - 2010-07-28

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Combinatorial Algorithms
  省略形 : IWOCA 2010
  副タイトル : 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
種別: 会議論文集
 著者・編者:
Iliopoulos, Costas S.1, 編集者
F. Smyth, William1, 編集者
所属:
1 External Organizations, ou_persistent22            
出版社, 出版地: Berlin : Springer
ページ: - 巻号: - 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-3-642-19221-0

出版物 2

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