Logo des Repositoriums
 
Textdokument

Computing Crossing Numbers: Berechnen von Kreuzungszahlen

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2009

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.

Beschreibung

Chimani, Markus (2009): Computing Crossing Numbers: Berechnen von Kreuzungszahlen. Ausgezeichnete Informatikdissertationen 2008. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-413-4. pp. 41-50

Schlagwörter

Zitierform

DOI

Tags