Return to search

Implementierung eines Algorithmus zur Partitionierung von Graphen

Partitionierung von Graphen ist im Allgemeinen sehr schwierig. Es stehen
derzeit keine Algorithmen zur Verfügung, die ein allgemeines Partitionierungsproblem
effizient lösen. Aus diesem Grund werden heuristische
Ansätze verfolgt.
Zur Analyse dieser Heuristiken ist man derzeit gezwungen zufällige Graphen
zu Verwenden. Daten realer Graphen sind derzeit entweder nur
sehr schwer zu erheben (z.B. Internetgraph), oder aus rechtlichen bzw.
wirtschaftlichen Gründen nicht zugänglich (z.B. soziale Netzwerke). Die
untersuchten Heuristiken liefern teilweise nur unter bestimmten Voraussetzungen
Ergebnisse. Einige arbeiten lediglich auf einer eingeschränkten
Menge von Graphen, andere benötigen zum Erkennen einer Partition
einen mit der Knotenzahl steigenden Durchschnittsgrad der Knoten, z.B.
[DHM04].
Der im Zuge dieser Arbeit erstmals implementierte Algorithmus aus
[CGL07a] benötigt lediglich einen konstanten Durchschnittsgrad der
Knoten um eine Partition des Graphen, wenn diese existiert, zu erkennen.
Insbesondere muss dieser Durchschnittsgrad nicht mit der Knotenzahl
steigen.
Nach der Implementierung erfolgten Tests des Algorithmus an zufälligen
Graphen. Diese Graphen entsprachen dem Gnp-Modell mit eingepflanzter Partition. Die untersuchten Clusterprobleme waren dabei große
Schnitte, kleine Schnitte und unabhängige Mengen. Der von der Art des
Clusterproblems abhängige Durchschnittsgrad wurde während der Tests
bestimmt.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa.de:swb:ch1-200701098
Date05 July 2007
CreatorsRiediger, Steffen
ContributorsTU Chemnitz, Fakultät für Informatik
PublisherUniversitätsbibliothek Chemnitz
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
Languagedeu
Detected LanguageGerman
Typedoc-type:StudyThesis
Formatapplication/pdf, text/plain, application/zip
RightsDokument ist für Print on Demand freigegeben

Page generated in 0.0017 seconds