TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 16.11.2016

isti-logo

Page Content

to Navigation

Heuristiken für das Entfernen von verbotenen Teilgraphen

Paul Walger (TU Berlin)

 

Graphen so zu modifizieren, dass sie gewisse induzierte Teilgraphen nicht mehr enthalten, ist bis auf gewisse triviale Fälle NP-vollständig. Dieses Problem ist unter dem Namen F-Free Edge Editing bekannt und hat als Eingabe einen Graphen und eine Menge von verbotenen Graphen. Für einige Mengen von verbotenen Teilgraphen wurde bereits gute Heuristiken entwickelt. Es werden Heuristiken für die Lösung des Problemes erarbeitet, indem drei verschiedene Ansätze entwickelt werden. Diese werden auf ihre Güte und Geschwindigkeit auf zufälligen und realen Datensätzen von Graphen getestet. Dafür wurde F-Free Edge Editing mittels Binary-Integer-Programming gelöst, um optimale Lösungen zu bestimmen. Außerdem werden diese allgemeinen Heuristiken mit spezifischen Heuristiken verglichen.

 

Date
Speaker
Location
Language
16.11.2016
16:15
Paul Walger
TEL 512
German

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe