Textdokument
Computing Crossing Numbers: Berechnen von Kreuzungszahlen
Lade...
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2009
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
In diesem Artikel betrachten wir das Problem der sogenannten Kreuzungszahl eines Graphen, d.h. die Anzahl von Kantenkreuzungen die unbedingt notwendig ist wenn man einen Graphen zeichnet. Das Problem ist NP-schwer und hat sich in den letzten Jahrzehnten auch als äußerst herausfordernd aus Sicht der graphentheoretischen und algorithmischen Forschung, sowie der Praxis, herausgestellt. Dennoch zeigen wir, dass sich Verfahren entwickeln lassen, die das Problem für viele praxisrelevante Graphen in annehmbarer Zeit beweisbar optimal lösen. Der Schlüssel dazu ist eine geschickte Kombination aus Graphentheorie, kombinatorischer Algorithmik, sowie algebraischen Methoden, insbesondere der Mathematischen Programmierung.