English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Exact algorithms for s-club finding and related problems

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

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-000E-72CF-5 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-002B-C13A-4
Genre: Thesis

Files

show Files
hide Files
:
da_schaefer.pdf (Preprint), 638KB
Name:
da_schaefer.pdf
Description:
-
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Schäfer, Alexander1, Author              
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s):
 Dates: 2009
 Publication Status: Published in print
 Pages: -
 Publishing info: Jena : Friedrich-Schiller-University
 Table of Contents: -
 Rev. Method: -
 Identifiers: -
 Degree: Diploma

Event

show

Legal Case

show

Project information

show

Source

show