Computing Crossing Numbers: Berechnen von Kreuzungszahlen

dc.contributor.author	Chimani, Markus
dc.contributor.editor	Hölldobler, Steffen
dc.date.accessioned	2020-08-21T08:42:14Z
dc.date.available	2020-08-21T08:42:14Z
dc.date.issued	2009
dc.description.abstract	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.	de
dc.identifier.isbn	978-3-88579-413-4
dc.identifier.pissn	1617-5468
dc.identifier.uri	https://dl.gi.de/handle/20.500.12116/33618
dc.language.iso	de
dc.publisher	Gesellschaft für Informatik
dc.relation.ispartof	Ausgezeichnete Informatikdissertationen 2008
dc.relation.ispartofseries	Lecture Notes in Informatics (LNI) - Dissertations, Volume D-9
dc.title	Computing Crossing Numbers: Berechnen von Kreuzungszahlen	de
gi.citation.endPage	50
gi.citation.publisherPlace	Bonn
gi.citation.startPage	41

Dateien

1 - 1 von 1