English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC07-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC08-2
Genre: Conference Paper

Files

show Files

Locators

show

Creators

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

Content

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

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-642-19222-7_34
BibTex Citekey: FernauFominLokshtanovMnichPhilipSaurabh2010
 Degree: -

Event

show
hide
Title: IWOCA 2010
Place of Event: London, United Kingdom
Start-/End Date: 2010-07-26 - 2010-07-28

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorial Algorithms
  Abbreviation : IWOCA 2010
  Subtitle : 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
Source Genre: Proceedings
 Creator(s):
Iliopoulos, Costas S.1, Editor
F. Smyth, William1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: ISBN: 978-3-642-19221-0

Source 2

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