Erweiterte
Suche ›

Parameterized Algorithmics for Network Analysis: Clustering & Querying

Buch
9,90 € Preisreferenz Lieferbar in 2-3 Tagen

Kurzbeschreibung

Diese 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.

Details
Schlagworte

Titel: Parameterized Algorithmics for Network Analysis: Clustering & Querying
Autoren/Herausgeber: Christian Komusiewicz
Ausgabe: Neuausgabe

ISBN/EAN: 9783798323797

Seitenzahl: 174
Format: 23 x 14,8 cm
Produktform: Taschenbuch/Softcover
Gewicht: 450 g
Sprache: Englisch

buchhandel.de - Newsletter
Möchten Sie sich für den Newsletter anmelden?


Bitte geben Sie eine gültige E-Mail-Adresse ein.
Lieber nicht