Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Hochschulschrift

Exact algorithms for s-club finding and related problems

MPG-Autoren
Es sind keine MPG-Autoren in der Publikation vorhanden
Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

da_schaefer.pdf
(Preprint), 638KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Schäfer, A. (2009). Exact algorithms for s-club finding and related problems. Diploma Thesis, Friedrich-Schiller-University, Jena.


Zitierlink: https://hdl.handle.net/11858/00-001M-0000-000E-72CF-5
Zusammenfassung
The Clique problem is one of the best-studied problems in computer science. However, there exist only few studies concerning the important Clique generalization, called the s-Club problem. In particular there have been no intensive investigations with respect to the parameterized complexity of this problem. In this thesis we show that s-Club is fixed-parameter tractable with respect to the number of vertices in the solution. In terms of polynomial time data reduction, we show that s-Club does not admit a polynomial many-to-one kernel. In contrast to that we give a cubic-vertex Turing kernel. In this context we also show an interesting connection to the approximation of a solution for s-Club, and give a combined algorithm to exploit this connection. Furthermore we study the complexity of s-Club on some restricted graph classes. In order to obtain efficient fixed-parameter algorithm, it is often useful to change the parameterization. Therefore, we analyze s-Club with a dual parameterization, which we define as the s-Club Vertex Deletion problem. We show that this problem is fixed-parameter tractable with respect to the number of vertices in the solution. We also introduce the s-Club Cluster Vertex Deletion problem, which is a generalization of the Cluster Vertex Deletion problem. For this problem we show NP-completeness and fixed-parameter tractability with respect to the combined parameter number of vertices in the solution and s.