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.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:17701 |
| Date | 05 July 2007 |
| Creators | Riediger, Steffen |
| Contributors | Technische Universität Chemnitz |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | German |
| Detected Language | German |
| Type | doc-type:StudyThesis, info:eu-repo/semantics/StudyThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds