A Tighter Insertion-based Approximation of the Crossing Number

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Přesnější aproximace průsečíkového čísla založená na vkládání
Autoři	CHIMANI Markus HLINĚNÝ Petr
Rok publikování	2011
Druh	Článek ve sborníku
Konference	Automata, Languages and Programming 38th International Colloquium, ICALP 2011
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	DOI
Doi	https://doi.org/10.1007/978-3-642-22006-7_11
Obor	Informatika
Klíčová slova	crossing number; crossing minimization; planar insertion
Popis	Podáme aproximační algoritmus pro problém vložení více hran do rovinného grafu. Toto zároveň dá nový aproximační algoritmus pro výpočet průsečíkového čísla grafu.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Graph Drawings and Representations