Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  A Single-exponential FPT Algorithm for the K4-Minor Cover Problem

Kim, E. J., Paul, C., & Philip, G. (2012). A Single-exponential FPT Algorithm for the K4-Minor Cover Problem. In F. V. Fomin, & P. Kaski (Eds.), Algorithm Theory - SWAT 2012 (pp. 119-130). Berlin: Springer.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-BDEF-A Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0023-C080-B
Genre: Konferenzbeitrag
Latex : A Single-exponential {FPT} Algorithm for the {K4-Minor} Cover Problem

Dateien

einblenden: Dateien
ausblenden: Dateien
:
swat-lncs.pdf (beliebiger Volltext), 336KB
 
Datei-Permalink:
-
Name:
swat-lncs.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kim, Eun Jung1, Autor
Paul, Christophe1, Autor
Philip, Geevarghese2, Autor           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Given an input graph G on \(n\) vertices and an integer k, the parameterized \textscK_4-minor cover} problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor free graph or, equivalently, in a graph of treewidth at most 2. The problem can thus also be called \textsc{Treewidth-2 Vertex Deletion}. This problem is inspired by two well-studied parameterized vertex deletion problems, \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}, which can be expressed as \textsc{Treewidth-t Vertex Deletion} problems: t=0 for {\sc Vertex Cover} and t=1 for {\sc Feedback Vertex Set}. While a single-exponential FPT algorithm has been known for a long time for \textsc{Vertex Cover}, such an algorithm for \textsc{Feedback Vertex Set} was devised comparatively recently. While it is known to be unlikely that \textsc{Treewidth-t Vertex Deletion} can be solved in time c^{o(k)}⋅ n^{O(1)}, it was open whether the \textsc{K_4-minor cover} could be solved in single-exponential FPT time, i.e. in c^k⋅ n^{O(1) time. This paper answers this question in the affirmative.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2012
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.1007/978-3-642-31155-0_11
BibTex Citekey: KimPaulPhilip2012
Anderer: Local-ID: B5AB1D87757A6B6EC1257ACE0013F370-KimPaulPhilip2012
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 13th Scandinavian Symposium and Workshops on Algorithm Theory
Veranstaltungsort: Helsinki, Finland
Start-/Enddatum: 2012-07-04 - 2012-07-06

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithm Theory - SWAT 2012
  Untertitel : 13th Scandinavian Symposium and Workshops
  Kurztitel : SWAT 2012
Genre der Quelle: Konferenzband
 Urheber:
Fomin, Fedor V.1, Herausgeber
Kaski, Petteri1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 119 - 130 Identifikator: ISBN: 978-3-642-31154-3

Quelle 2

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