Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

Philip, G., Raman, V., & Sikdar, S. (2009). Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels. In A. Fiat, & P. Sanders (Eds.), Algorithms - ESA 2009 (pp. 694-705). Berlin: Springer. doi:10.1007/978-3-642-04128-0_62.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC09-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-DC0A-D
Genre: Konferenzbeitrag
Latex : Solving Dominating Set in Larger Classes of Graphs: {FPT} Algorithms and Polynomial Kernels

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Philip, Geevarghese1, Autor           
Raman, Venkatesh1, Autor
Sikdar, Somnath1, Autor
Affiliations:
1External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: We show that the \nounk-Dominating Set} problem is fixed parameter tractable (FPT) and has a polynomial kernel for any class of graphs that exclude K_{i,j as a subgraph, for any fixed i,j≥1. This strictly includes every class of graphs for which this problem has been previously shown to have FPT algorithms and/or polynomial kernels. In particular, our result implies that the problem restricted to bounded-degenerate graphs has a polynomial kernel, solving an open problem posed by Alon and Gutner.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20092009
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.1007/978-3-642-04128-0_62
BibTex Citekey: PhilipRamanSikdar2009
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: ESA 2009
Veranstaltungsort: Copenhagen, Denmark
Start-/Enddatum: 2009-09-07 - 2009-09-09

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Algorithms - ESA 2009
  Untertitel : 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings
  Kurztitel : ESA 2009
Genre der Quelle: Konferenzband
 Urheber:
Fiat, Amos1, Herausgeber
Sanders, Peter1, Herausgeber           
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Berlin : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 694 - 705 Identifikator: ISBN: 978-3-642-04127-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: 5757 Artikelnummer: - Start- / Endseite: - Identifikator: -