Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  A Quartic Kernel for Pathwidth-One Vertex Deletion

Philip, G., Raman, V., & Villanger, Y. (2010). A Quartic Kernel for Pathwidth-One Vertex Deletion. In D. M. Thilikos (Ed.), Graph Theoretic Concepts in Computer Science (pp. 196-207). Berlin: Springer. doi:10.1007/978-3-642-16926-7_19.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Philip, Geevarghese1, Autor           
Raman, Venkatesh1, Autor
Villanger, Yngve1, Autor
Affiliations:
1External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is \npc{}. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G=(V,E),k);|V|=n, we can construct, in polynomial time, an instance (G',k') such that (i) (G,k) is a YES instance if and only if (G',k') is a YES instance, (ii) G' has \Oh(k^4}) vertices, and (iii) k'≤ k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in \Oh(7^{kk⋅ n²) time.

Details

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

Veranstaltung

einblenden:
ausblenden:
Titel: WG 2010
Veranstaltungsort: Crete, Greece
Start-/Enddatum: 2010-06-28 - 2010-06-30

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Graph Theoretic Concepts in Computer Science
  Kurztitel : WG 2010
  Untertitel : 36th International Workshop, WG 2010, Zarós, Crete, Greece, June 28-30, 2010 Revised Papers
Genre der Quelle: Konferenzband
 Urheber:
Thilikos, Dimitrios M.1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 196 - 207 Identifikator: ISBN: 978-3-642-16925-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: 6410 Artikelnummer: - Start- / Endseite: - Identifikator: -