Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
Zur Ablage hinzufügen
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  The Effect of Girth on the Kernelization Complexity of Connected Dominating Set

Misra, N., Philip, G., Raman, V., & Saurabh, S. (2010). The Effect of Girth on the Kernelization Complexity of Connected Dominating Set. In K. Lodaya, & M. Mahajan (Eds.), 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (pp. 96-107). Wadern: Schloss Dagstuhl. doi:10.4230/LIPIcs.FSTTCS.2010.96.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D517-B Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-D51D-0
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
http://drops.dagstuhl.de/opus/volltexte/2010/2856/ (beliebiger Volltext)
Beschreibung:
-
OA-Status:

Urheber

einblenden:
ausblenden:
 Urheber:
Misra, Neeldhara1, Autor
Philip, Geevarghese1, Autor           
Raman, Venkatesh1, Autor
Saurabh, Saket1, Autor
Affiliations:
1External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: In the Connected Dominating Set problem we are given as input a graph G and a positive integer k, and are asked if there is a set S of at most k vertices of G such that S is a dominating set of G and the subgraph induced by S is connected. This is a basic connectivity problem that is known to be NP-complete, and it has been extensively studied using several algorithmic approaches. In this paper we study the effect of excluding short cycles, as a subgraph, on the \em kernelization complexity} of Connected Dominating Set. Kernelization algorithms are polynomial-time algorithms that take an input and a positive integer k (the {\em parameter}) and output an equivalent instance where the size of the new instance and the new parameter are both bounded by some function g(k). The new instance is called a g(k) {\em kernel} for the problem. If g(k) is a polynomial in k then we say that the problem admits polynomial kernels. The girth of a graph G is the length of a shortest cycle in G. It turns out that Connected Dominating Set is ``hard'' on graphs with small cycles, and becomes progressively easier as the girth increases. More specifically, we obtain the following interesting trichotomy: Connected Dominating Set \begin{itemize} \item does not have a kernel of {\em any} size on graphs of girth 3 or 4 (since the problem is W[2]-hard); \item admits a g(k) kernel, where g(k) is k^{O(k)}, on graphs of girth 5 or 6 but has {\em no} polynomial kernel (unless the Polynomial Hierarchy (PH) collapses to the third level) on these graphs; \item has a cubic (O(k^3)) kernel on graphs of girth at least 7. \end{itemize} While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded {\em minors}, our results add to the very few known in the field for graph classes characterized by excluded {\em subgraphs.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 20102010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: DOI: 10.4230/LIPIcs.FSTTCS.2010.96
BibTex Citekey: MisraPhilipRamanSaurabh2010
URN: urn:nbn:de:0030-drops-28567
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 30th International Conference on Foundations of Software Technology and Theoretical Computer Science Science
Veranstaltungsort: Chennai, India
Start-/Enddatum: 2010-12-15 - 2010-12-18

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: 30th International Conference on Foundations of Software Technology and Theoretical Computer Science
  Kurztitel : FSTTCS 2010
  Untertitel : FSTTCS 2010, December 15–18, 2010, Chennai, India
Genre der Quelle: Konferenzband
 Urheber:
Lodaya, Kamal1, Herausgeber
Mahajan, Meena1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: Wadern : Schloss Dagstuhl
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 96 - 107 Identifikator: ISBN: 978-3-939897-23-1

Quelle 2

einblenden:
ausblenden:
Titel: Leibniz International Proceedings in Informatics
  Kurztitel : LIPIcs
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 8 Artikelnummer: - Start- / Endseite: - Identifikator: -