de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  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

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0019-DC07-4 Version Permalink: http://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, escidoc: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: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 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, escidoc: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: -