Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC07-4 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC08-2
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Fernau, Henning1, Autor
Fomin, Fedor V.1, Autor
Lokshtanov, Daniel1, Autor
Mnich, Matthias1, Autor
Philip, Geevarghese1, Autor           
Saurabh, Saket1, Autor
Affiliations:
1External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20112011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.1007/978-3-642-19222-7_34
BibTex Citekey: FernauFominLokshtanovMnichPhilipSaurabh2010
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: IWOCA 2010
Veranstaltungsort: London, United Kingdom
Start-/Enddatum: 2010-07-26 - 2010-07-28

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Combinatorial Algorithms
  Kurztitel : IWOCA 2010
  Untertitel : 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
Genre der Quelle: Konferenzband
 Urheber:
Iliopoulos, Costas S.1, Herausgeber
F. Smyth, William1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: ISBN: 978-3-642-19221-0

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
  Kurztitel : LNCS
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 6460 Artikelnummer: - Start- / Endseite: - Identifikator: -