Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Fernau, Henning Fomin, Fedor V. Lokshtanov, Daniel Mnich, Matthias Philip, Geevarghese Saurabh, Saket dblp dblp dblp dblp dblp dblp Not MPG Author(s): Fernau, Henning Fomin, Fedor V. Lokshtanov, Daniel Mnich, Matthias Saurabh, Saket
 Editor(s): Iliopoulos, Costas S. F. Smyth, William dblp dblp Not MPII Editor(s): Iliopoulos, Costas S. F. Smyth, William
 BibTeX cite key*: FernauFominLokshtanovMnichPhilipSaurabh2010

 Title, Booktitle
 Title*: Ranking and Drawing in Subexponential Time oscm-kemeny.pdf (445.15 KB) Booktitle*: Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers

 Event, URLs
 URL of the conference: http://www.iwoca.org/iwoca2010/ URL for downloading the paper: http://www.springerlink.com/content/q36576727026h272/fulltext.pdf Event Address*: London, United Kingdom Language: English Event Date* (no longer used): Organization: Event Start Date: 26 July 2010 Event End Date: 28 July 2010

 Publisher
 Name*: Springer URL: http://www.springer.com Address*: Berlin Type: Revised Selected Papers

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 6460 Number: Month: Pages: Year*: 2011 VG Wort Pages: ISBN/ISSN: 978-3-642-19221-0 Sequence Number: DOI: 10.1007/978-3-642-19222-7_34

 (LaTeX) 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$]). URL for the Abstract: http://www.springerlink.com/content/q36576727026h272/ Keywords: Kemeny Aggregation, One-Sided Crossing Minimization, Parameterized Complexity, Subexponential-time Algorithms, Social Choice Theory, Graph Drawing, Directed Feedback Arc Set Copyright Message: Copyright Springer-Verlag Berlin Heidelberg 2011. This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, speciﬁcally the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microﬁlms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Published in the Proceedings of IWOCA 2010, London, United Kingdom, July 26-28, 2010. Lecture Notes in Computer Science, Volume 6460. The original publication is available at www.springerlink.com : http://www.springerlink.com/content/q36576727026h272/ Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{FernauFominLokshtanovMnichPhilipSaurabh2010,
AUTHOR = {Fernau, Henning and Fomin, Fedor V. and Lokshtanov, Daniel and Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket},
EDITOR = {Iliopoulos, Costas S. and F. Smyth, William},
TITLE = {Ranking and Drawing in Subexponential Time},
BOOKTITLE = {Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers},
PUBLISHER = {Springer},
YEAR = {2011},
TYPE = {Revised Selected Papers},
VOLUME = {6460},
SERIES = {Lecture Notes in Computer Science},