A Tighter Insertion-based Approximation of the Crossing Number

• 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
• www: DOI
• Doi: http://dx.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