Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3031
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorNiedermeier, Rolfen
dc.contributor.authorKomusiewicz, Christianen
dc.date.accessioned2015-11-20T20:54:01Z-
dc.date.available2011-11-23T12:00:00Z-
dc.date.issued2011-11-23-
dc.date.submitted2011-11-23-
dc.identifier.isbn978-3-7983-2380-3-
dc.identifier.uriurn:nbn:de:kobv:83-opus-32503-
dc.identifier.urihttp://depositonce.tu-berlin.de/handle/11303/3328-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-3031-
dc.descriptionZugleich gedruckt veröffentlicht im Universitätsverlag der TU Berlin unter der ISBN 978-3-7983-2379-7.en
dc.description.abstractDiese Arbeit beschäftigt sich mit der parametrisierten Komplexität NP-schwerer Berechnungsprobleme aus zwei Bereichen der Netzwerkanalyse: dem Clustern von Netzwerken und dem Querying von Netzwerken. Der Fokus liegt hierbei auf der Identifizierung neuer problemspezifischer Parameter, welche als Basis für effiziente Algorithmen für diese Probleme dienen können. Die entscheidende Frage für ein Problem und einen Parameter k ist dabei, ob das Problem festparameterhandhabbar bezüglich k ist, d.h. ob Instanzen der Größe n in f(k)*poly(n) Zeit gelöst werden kann, wobei f eine beliebige berechenbare Funktion und poly eine polynomielle Funktion ist. Im Gegensatz dazu können Probleme, welche schwer bezüglich der Komplexitätsklasse W[1] sind, wahrscheinlich nicht in dieser Laufzeit gelöst werden. In dieser Arbeit werden sowohl Festparameterhandhabbarkeits- als auch W[1]-Schwere-Resultate für Probleme aus den beiden genannten Anwendungsgebieten präsentiert. Das Clustern von Netzwerken ist die Aufgabe, die Knotenmenge eines Netzwerks in homogene Gruppen, die Cluster, aufzuteilen. Grundlage für die Clusterung bilden dabei die Kanten des Netzwerks. Den Ausgangspunkt unserer Studien zum Netzwerkclustern bildet das NP-schwere und in der Literatur bereits intensiv studierte Cluster Editing-Problem. In dieser Arbeit werden zunächst neue Parametrisierungen von Cluster Editing untersucht und untere Laufzeitschranken bezüglich des Parameters "Lösungsgröße" bewiesen. Zudem wird die parametrisierte Komplexität verschiedener Verallgemeinerungen von Cluster Editing und des verwandten Consensus Clustering-Problems untersucht. Das Querying von Netzwerken ist die Aufgabe, für ein gegebenes kleines Netzwerk (die Query) ein möglichst ähnliches Teilnetzwerk innerhalb eines großen Netzwerks (des Hosts) zu suchen. Dieses ähnliche Teilnetzwerk heißt dann "Vorkommen der Query". Wir präsentieren Festparameterhandhabbarkeits- und W[1]-Schwere-Resultate für den Fall, dass die Query ein dichter Graph ist, für den Fall, dass das Vorkommen der Query bestimmte Zusammenhangseigenschaften erfüllt und für den Fall, dass für die Queryknoten die Anzahl ähnlicher Knoten im Host beschränkt ist. Gedruckte Version im Universitätsverlag der TU Berlin(www.univerlag.tu-berlin.de) erschienen, Format A5, ISBN 978-3-7983-2379-7de
dc.description.abstractThis thesis studies the parameterized computational complexity of NP-hard problems that have applications in two areas of network analysis: clustering and querying. In particular, we aim at identifying parameters that describe the complexity of the computational problems and may thus serve as basis for efficient algorithms for these problems. Network clustering is the task of assigning the vertices of the network into groups such that the groups contain network vertices that are similar to each other. The origin of our investigations for network clustering is the well-studied NP-hard Cluster Editing problem. We extend previous work on Cluster Editing by showing NP-hardness and running time lower bounds for restricted cases of Cluster Editing, and by presenting parameterized algorithms for NP-hard generalizations and variants of Cluster Editing such as Consensus Clustering. Network querying is the task of finding a subnetwork of a large host network that is similar to a given small network, the query. Network querying problems are related to the Subgraph Isomorphism problem and therefore usually NP-hard. We present parameterized algorithms and hardness results for dense queries, for topology-free querying, and for the case that for each query vertex the number of similar vertices in the host is bounded. Printed Version published by Universitätsverlag der TU Berlin (www.univerlag.tu-berlin.de), DIN A5, ISBN 978-3-7983-2379-7en
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.otherGraphalgorithmende
dc.subject.otherNP-schwere Problemede
dc.subject.otherProteininteraktionsnetzwerkede
dc.subject.otherGraph algorithmsen
dc.subject.otherNP-hard problemsen
dc.subject.otherProtein interaction networksen
dc.titleParameterized Algorithmics for Network Analysisen
dc.typeDoctoral Thesisen
tub.accessrights.dnbfree*
tub.publisher.universityorinstitutionUniversitätsverlag der TU Berlinen
dc.contributor.grantorTechnische Universität Berlin, Fakultät IV - Elektrotechnik und Informatiken
dc.date.accepted2011-07-14-
dc.publisher.nameUniversitätsverlag der TU Berlinen
dc.publisher.placeBerlinen
dc.title.subtitleClustering and Queryingen
dc.title.translatedParametrisierte Algorithmik für die Netzwerkanalysede
dc.title.translatedsubtitleClustering und Queryingde
dc.type.versionpublishedVersionen
tub.identifier.opus33250-
tub.identifier.opus43146-
Appears in Collections:Inst. Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
Dokument_52.pdf

Text

Format: Adobe PDF | Size: 1.1 MB
DownloadShow Preview
Thumbnail
Dokument_53.pdf

Umschlag

Format: Adobe PDF | Size: 21.61 MB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.