Logo des Repositoriums
 

Computing Crossing Numbers: Berechnen von Kreuzungszahlen

dc.contributor.authorChimani, Markus
dc.contributor.editorHölldobler, Steffen
dc.date.accessioned2020-08-21T08:42:14Z
dc.date.available2020-08-21T08:42:14Z
dc.date.issued2009
dc.description.abstractIn 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.de
dc.identifier.isbn978-3-88579-413-4
dc.identifier.pissn1617-5468
dc.identifier.urihttps://dl.gi.de/handle/20.500.12116/33618
dc.language.isode
dc.publisherGesellschaft für Informatik
dc.relation.ispartofAusgezeichnete Informatikdissertationen 2008
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Dissertations, Volume D-9
dc.titleComputing Crossing Numbers: Berechnen von Kreuzungszahlende
gi.citation.endPage50
gi.citation.publisherPlaceBonn
gi.citation.startPage41

Dateien

Originalbündel
1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
41.pdf
Größe:
356.39 KB
Format:
Adobe Portable Document Format