edoc-Server der Humboldt-Universität zu Berlin

Dissertation

Autor(en): Stefan Kirchner
Titel: Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen
Gutachter: Mihyun Kang; Stefan Hougardy; Anand Srivastav
Erscheinungsdatum: 02.09.2008
Volltext: pdf (urn:nbn:de:kobv:11-10092400)
Fachgebiet(e): Informatik
Schlagwörter (ger): Steinerbaum, Approximationsalgorithmen, untere Schranken, Bicliquen
Schlagwörter (eng): Steiner tree, approximation algorithms, lower bounds, bicliques
Einrichtung: Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II
Zitationshinweis: Kirchner, Stefan: Untere Schranken für Steinerbaumalgorithmen und die Konstruktion von Bicliquen in dichten Graphen; Dissertation, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 02.09.2008, urn:nbn:de:kobv:11-10092400
Metadatenexport: Um den gesamten Metadatensatz im Endnote- oder Bibtex-Format zu speichern, klicken Sie bitte auf den entsprechenden Link. Endnote   Bibtex  
print on demand: Wenn Sie auf dieses Icon klicken, können Sie ein Druckexemplar dieser Publikation bestellen.
Diese Seite taggen: Diese Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer ansehen können.
  • connotea
  • del.icio.us
  • Furl
  • RawSugar

Abstract (ger):
Die vorliegende Arbeit besteht aus zwei Teilen. Der erste Teil der Arbeit befasst sich mit unteren Schranken für approximative Steinerbaumalgorithmen. Ein Steinerbaum ist ein kürzester Teilgraph, der eine gegebene Teilmenge der Knoten eines Graphen spannt. Das Berechnen eines Steinerbaumes ist ein klassisches NP-schweres Problem, und es existieren mehrere Approximationsalgorithmen, wobei bei den meisten Algorithmen die Approximationsgüte nur durch untere und obere Schranken eingegrenzt werden kann. Für einige dieser Algorithmen werden in dieser Arbeit Instanzen vorgestellt, welche die unteren Schranken verbessern. Für den Relativen Greedy Algorithmus wird außerdem ein Verfahren vorgestellt, mit dem die Güte des Algorithmus eingeschränkt auf die Graphenklasse mit k Terminalen auf einen beliebigen Faktor genau bestimmt werden kann. Der zweite Teil der Arbeit widmet sich vollständig bipartiten Subgraphen mit gleicher Partitionsgrößse, sogenannten balancierten Bicliquen. Seit langem ist bekannt, dass in dichten bipartiten Graphen balancierte Bicliquen mit Omega(log(n)) Knoten existieren, aber es ist unbekannt, ob und wie diese in polynomieller Zeit konstruiert werden können. Der zweite Teil liefert dazu einen Beitrag, indem ein polynomieller Algorithmus vorgestellt wird, der in hinreichend großen dichten bipartiten Graphen eine balancierte Biclique mit Omega(sqrt(log(n))) Knoten konstruiert.
Abstract (eng):
This thesis consists of two parts. The first part is concerned with lower bounds for approximating Steiner trees. The Steiner tree problem is to find a shortest subgraph that spans a given set of vertices in a graph and is a classical NP-hard problem. Several approximation algorithms exist, but for most algorithms only lower and upper bounds for the approximation ratio are known. For some of these algorithms we present instances which improve the lower bounds. When the problem is restricted to the class of graphs with k terminals, we also present a method which can be used to determine the approximation ratio of the Relative Greedy Algorithm with arbitrary precision. The second part is about balanced bicliques, i.e. complete bipartite subgraphs with equal partition sizes. It has been known for a long time that every dense bipartite graph contains a balanced biclique of size Omega(log(n)), but whether and how such a biclique can be constructed in polynomial time is still unknown. Our contribution to this problem is a polynomial time algorithm which constructs a balanced biclique of size Omega(sqrt(log(n))) in sufficiently large and dense bipartite graphs.
Zugriffsstatistik: Die Daten für die Zugriffsstatistik der einzelnen Dokumente wurden aus den durch AWStats aggregierten Webserver-Logs erstellt. Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
 
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen (insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert auf eine der Dateien (Kapitel) des Dokuments angezeigt.
 
Um die detaillierten Zugriffszahlen zu sehen, fahren Sie bitte mit dem Mauszeiger über die einzelnen Balken des Diagramms.
Startseite: 14 Zugriffe PDF: 5 Zugriffe Startseite: 4 Zugriffe PDF: 10 Zugriffe Startseite: 4 Zugriffe PDF: 8 Zugriffe Startseite: 17 Zugriffe PDF: 8 Zugriffe Startseite: 14 Zugriffe PDF: 13 Zugriffe Startseite: 8 Zugriffe PDF: 7 Zugriffe Startseite: 8 Zugriffe PDF: 10 Zugriffe PDF: 7 Zugriffe PDF: 9 Zugriffe Startseite: 2 Zugriffe PDF: 7 Zugriffe Startseite: 5 Zugriffe PDF: 15 Zugriffe PDF: 8 Zugriffe PDF: 2 Zugriffe PDF: 11 Zugriffe PDF: 12 Zugriffe PDF: 11 Zugriffe PDF: 21 Zugriffe PDF: 25 Zugriffe Startseite: 3 Zugriffe PDF: 29 Zugriffe Startseite: 3 Zugriffe PDF: 19 Zugriffe Startseite: 2 Zugriffe PDF: 35 Zugriffe Startseite: 4 Zugriffe PDF: 22 Zugriffe Startseite: 10 Zugriffe PDF: 22 Zugriffe Startseite: 11 Zugriffe PDF: 18 Zugriffe Startseite: 84 Zugriffe PDF: 14 Zugriffe Startseite: 2 Zugriffe PDF: 27 Zugriffe Startseite: 5 Zugriffe PDF: 29 Zugriffe Startseite: 2 Zugriffe PDF: 26 Zugriffe Startseite: 5 Zugriffe PDF: 29 Zugriffe Startseite: 18 Zugriffe PDF: 32 Zugriffe Startseite: 17 Zugriffe PDF: 39 Zugriffe
Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Monat Jul
11
Aug
11
Sep
11
Oct
11
Nov
11
Dec
11
Feb
12
Apr
12
May
12
Jun
12
Jul
12
Aug
12
Sep
12
Oct
12
Nov
12
Dec
12
Jan
13
Feb
13
Mar
13
Apr
13
May
13
Jun
13
Jul
13
Aug
13
Sep
13
Oct
13
Nov
13
Dec
13
Jan
14
Feb
14
Mar
14
Startseite 14 4 4 17 14 8 8     2 5               3 3 2 4 10 11 84 2 5 2 5 18 17
PDF 5 10 8 8 13 7 10 7 9 7 15 8 2 11 12 11 21 25 29 19 35 22 22 18 14 27 29 26 29 32 39

Gesamtzahl der Zugriffe seit Jul 2011:

  • Startseite – 242 (7.81 pro Monat)
  • PDF – 530 (17.1 pro Monat)
 
 
Generiert am 19.04.2014, 03:43:51