Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Aproximace průsečíkového čísla grafů nakreslitelných na orientovaných plochách
Autoři	HLINĚNÝ Petr CHIMANI Markus
Rok publikování	2010
Druh	Článek ve sborníku
Konference	ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)
Fakulta / Pracoviště MU	Fakulta informatiky
Citace	HLINĚNÝ, Petr a Markus CHIMANI. Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. Online. In ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). USA, internet: SIAM / ACM, 2010, s. 918-927. ISBN 978-0-89871-698-6.
www	conference Proceedings address
Obor	Informatika
Klíčová slova	crossing number; crossing minimization; surface
Popis	Podáme $O(n\log n)$ algoritmus s konstantním aproximačním faktorem pro průsečíkové číslo grafu G omezeného stupně, který má husté nakreslení na libovolném fixním orientovaném povrchu.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti