A Tighter Insertion-based Approximation of the Graph Crossing Number

• Název česky: Těsnější aproximace průsečíkového čísla na základě vkládání
• Autoři: HLINĚNÝ Petr; CHIMANI Markus
• Rok publikování: 2011
• Druh: Vyžádané přednášky
• Fakulta / Pracoviště MU: Fakulta informatiky
• 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
• Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
• Graph Drawings and Representations