34
Frozen Development in Graph Coloring Sarah Tauscher 16. Juni 2008

Frozen Development in Graph Coloring

  • Upload
    macon

  • View
    35

  • Download
    0

Embed Size (px)

DESCRIPTION

Frozen Development in Graph Coloring. Sarah Tauscher 16. Juni 2008. Gliederung. Motivation Vorstellung des Verfahrens Vergleich der Implementierungsvarianten Ergebnisse Weiterführende Untersuchungen Einfluss freier Paare Entwicklung der Äquivalenzklassen Minimale Graphen - PowerPoint PPT Presentation

Citation preview

Page 1: Frozen Development in Graph Coloring

Frozen Development in Graph Coloring

Sarah Tauscher

16. Juni 2008

Page 2: Frozen Development in Graph Coloring

Gliederung

Motivation Vorstellung des Verfahrens

Vergleich der Implementierungsvarianten Ergebnisse

Weiterführende Untersuchungen Einfluss freier Paare Entwicklung der Äquivalenzklassen

Minimale Graphen Konstruktion kritischer Graphen

Ausblick

Page 3: Frozen Development in Graph Coloring

Motivation

Average-Case-Analyse np-vollständiger Probleme Ziel: Eigenschaften zu identifizieren die Einfluss auf die

Schwierigkeiten der Lösung einzelner Instanzen haben Untersuchung von Zufallsinstanzen mit Methoden aus

der statistischen Mechanik Phasenübergang von färbbaren zu unfärbaren Graphen

in Zufallsgraphprozessen bei Erhöhung des Durchschnittsgrads

Schwellwert: Wert des Durchschnittsgrads zu dem der Phasenübergang erfolgt

Ordnungsparameter: Eigenschaften die Veränderung beim Phasenübergang charakterisieren

Page 4: Frozen Development in Graph Coloring

Full Frozen Development

Zufallsgraphprozess in dessen Verlauf nur Kanten hinzugefügt werden, falls der Graph färbbar bleibt

Bestimmung der Paartypen fixierte Paare, sind diejenigen die in allen gültigen Färbungen

gleich gefärbt sind freie Paare sind in allen gültigen Färbungen unterschiedlich

gefärbt, obwohl sie nicht verbunden sind Paare die weder frei noch fixiert sind, sind effektiv Die Bestimmung erfolgt durch Widerspruch

Bestimmung der Kristallisationsindices Backbone wird als Approximation des Ordnungs-

parameters verwendet

Page 5: Frozen Development in Graph Coloring

Implementierungsvarianten

Vorwärtsscan (VS) bei jedem Index,

werden alle Paare mit größeren Index kontrolliert, ob ihr Typ bestimmt ist

Anzahl der Aufrufe des Graphfärbeprogramms O(n4)

es werden hauptsächlich färbbare Graphen getestet

Rückwärtsscan (RS) zu dem aktuellem

Paar wird sein Typ und Kristallisations-index bestimmt

O(n2log(n2)) Verhältnis von

färbbaren zu unfärbbaren Graphen ist ungefähr gleich

Page 6: Frozen Development in Graph Coloring

Optimierungen

Wiederverwenden schon erstellter gültiger Färbungen Reduzierung gültiger Aufrufe Beim RS muss gespeichert werden bis zu welchem

Index die Färbung gültig ist Ausnutzen der Äquivalenzrelation

Reduzierung ungültiger Aufrufe bei beiden Varianten Bei RS auch Einsparung gültiger Aufrufe bei der

Bestimmung des Kristallisationsindex Vorrausberechnung des Schwellwertes

Alle Paare mit kleinerem Index als der Schwellwert sind nicht fixiert

Page 7: Frozen Development in Graph Coloring

Experimente für den Vergleich der Varianten je 30 Zufallsgraphprozesse der Ordnungen 50,75,..., 225 VS, RS ohne und mit Ausnutzen der Äquivalenzfunktion

und diese wiederum mit und ohne Schwellwertvorraus-berechnung

gesammelte Daten: Anzahl der Aufrufe und Suchknoten, getrennt nach färbbar und

unfärbbar Anzahl der durch die Äquivalenzrelation bestimmbaren

Paartypen Aufrufe für die Schwellwertvorausberechnung Für RS die Anzahl der Färbungen die durch Wiederverwenden

von Färbungen eingespart werden Laufzeit

Page 8: Frozen Development in Graph Coloring

Anzahl der Aufrufe

Page 9: Frozen Development in Graph Coloring

Eigenschaften der untersuchten Graphen

Anzahl der Knoten pro Farbe in vollständigen Graphen annähernd gleich

Verteilung der Typen abhängig vom Zufallsgraphprozess

Page 10: Frozen Development in Graph Coloring

Kantentypen

Kantenmaximaler Graph ist eindeutig färbbar, aber nicht minimal

Zwei Kantentypen: effektive Kanten: Wird dies Kante entfernt können ihre

Knoten gleich gefärbt werden freie Kanten: Nach Entfernung der Kante bilden die

Knoten ein freies Paar Untere Schranke: 2* (n-3) + 3 Bestimmung der Kantentypen nicht eindeutig Anteil freier Kanten liegt bei ca17%

Page 11: Frozen Development in Graph Coloring

Ergebnisse

Anzahl fixierter Paare steigt beim Phasenübergang stark an

Anstieg wird für Graphprozesse höherer Ordnung steiler

Page 12: Frozen Development in Graph Coloring

Auftreten freier Paare

Auftreten analog zu dem fixierter Paare

Alle Nachbarn eines Knoten eines fixierten Paares bilden ein freies Paar mit dem anderen Knoten

Freie Paare treten auch ohne fixierte Paare auf

Page 13: Frozen Development in Graph Coloring

Einfluss freier Paare auf die Kosten der Färbungen

Werden beim VS alle bekannten freien Paare als Kante hinzugefügt, werden die Färbungen „einfacher“

Es treten deutlich mehr 4-Cliquen auf Erhöhung des Durchschnittsgrades Struktur der Graphen nach Hinzufügen freier Paare

Vereinfachung der Färbungen ist auch bei 4-COL zu beobachten

Page 14: Frozen Development in Graph Coloring

Beweise

F+(K-COL) ist np-vollständig Graphen sind entweder k-färbbar, oder besitzen eine

N4C mit Sehne s und ohne s ist der Graph k-färbbar und besitzt keine freien Paare

Reduktion: Die Bestimmung eines freien Paares ist np-

vollständig Die Bestimmung, ob ein Paar frei ist, ist np-

vollständig

Page 15: Frozen Development in Graph Coloring

Kollabierter Graph

Äquivalenzklassen werden zu einem Knoten zusammengefasst

Größe des kollabierten Graphen reduziert sich bei einem Index um ca 28% (min. 10%)

Index der die größte Reduzierung verursacht wird als Max-Drop bezeichnet

Page 16: Frozen Development in Graph Coloring

Äquivalenzklassen

Mögliche Ursachen für Max-Drop Entstehung neuer Äquivalenzklassen Hinzufügen von Knoten zu vorhandenen Klassen Zusammenfall von Äquivalenzklassen

Anstieg der Anzahl der Äquivalenzklassen Typischerweise stärker in Schwellwertnähe

Wachstum der Äquivalenzklassen Großteil der Klassen wächst nur um wenige Knoten Maximale Werte werden für Graphprozesse höherer

Ordnung größer, treten sehr selten auf

Page 17: Frozen Development in Graph Coloring

Minimale Graphen (1)

Graphen enthalten mindestens ein freies oder fixiertes Paar

Nach Entfernung einer beliebigen Kante, weist der Graph weder freie noch fixierte Paare auf

Zur Konstruktion minimaler Graphen ist es hilfreich die Bedingungen die von den Nachbarn freier und fixierter Paare erfüllt sein müssen zu betrachten

Page 18: Frozen Development in Graph Coloring

Minimale Graphen (2)

Page 19: Frozen Development in Graph Coloring

Konstruktion minimale Graphen mit mehreren freien und fixierten Paaren Ein Dreieck und ein Kreis

dessen Länge durch 3 teilbar ist

Page 20: Frozen Development in Graph Coloring

Minimale Graphen (3)

Ein Dreieck und ein Kreis dessen Länge durch 3 teilbar ist

Verbinde die Knoten des Kreises abwechselnd mit einem Knoten des Dreiecks

Page 21: Frozen Development in Graph Coloring

Minimale Graphen (3)

Ein Dreieck und ein Kreis dessen Länge durch 3 teilbar ist

Verbinde die Knoten des Kreises abwechselnd mit einem Knoten des Dreiecks

Alle Knoten die mit dem gleichen Dreiecksknoten verbunden sind gehören zu einer Äquivalenz-klasse

Page 22: Frozen Development in Graph Coloring

Konstruktion kritischer Graphen

Ausgangspunkt ein kritischer Graph

Page 23: Frozen Development in Graph Coloring

Konstruktion kritischer Graphen

Ausgangspunkt ein kritischer Graph

Ersetzen einer Kante durch ein freies Paar, eines minimalen Graphen

Page 24: Frozen Development in Graph Coloring

Konstruktion kritischer Graphen

Ausgangspunkt ein kritischer Graph

Ersetzen einer Kante durch ein freies Paar eines minimalen Graphen

Ersetzen eines Knotens durch ein fixiertes Paar eines minimalen Graphen

Page 25: Frozen Development in Graph Coloring

Ausblick

Optimierung der Laufzeit des Full Frozen Developments Testen der konstruierten kritischen Graphen Entwicklung von Algorithmen zur Konstruktion kritischer

Graphen aus minimalen Graphen Bestimmung minimaler Strukturen für k > 3 Anwendung des Frozen Developments zur Bestimmung

minimaler Graphen Testen anderer Färbeprogramme Durchführen des Full Frozen Developments für k > 3

Page 26: Frozen Development in Graph Coloring

Vielen Dank für die Aufmerksamkeit

Fragen ?

Page 27: Frozen Development in Graph Coloring

Berechnung der Anzahl der Färbungen ohne Optimierungen

Page 28: Frozen Development in Graph Coloring

Kristalisationsindices

Page 29: Frozen Development in Graph Coloring

Variablen-Gadgets

Page 30: Frozen Development in Graph Coloring

Klausel-Gadgets

Page 31: Frozen Development in Graph Coloring

Laufzeit

Page 32: Frozen Development in Graph Coloring

Kritische Graphen

Page 33: Frozen Development in Graph Coloring

Formeln

Page 34: Frozen Development in Graph Coloring

Kollabierter Graph