Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface

Logo poskytovatele

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
www
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.