2007
Approximating the Crossing Number of Toroidal Graphs
HLINĚNÝ, Petr a Gelasio SALAZARZákladní údaje
Originální název
Approximating the Crossing Number of Toroidal Graphs
Název česky
Aproximace průsečíkového čísla toroidálních grafů
Autoři
HLINĚNÝ, Petr ORCID a Gelasio SALAZAR
Vydání
Berlin, International Symposium on Algorithms and Computation (ISAAC 2007), s. 148-159, 2007
Nakladatel
Springer Verlag
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Označené pro přenos do RIV
Ano
Kód RIV
RIV/00216224:14330/07:00020423
Organizační jednotka
Fakulta informatiky
ISBN
978-3-540-77118-0
UT WoS
Klíčová slova anglicky
crossing number; crossing minimization; approximation
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 12. 6. 2008 10:56, prof. RNDr. Petr Hliněný, Ph.D.
V originále
CrossingNumber is one of the most challenging algorithmic problems in topological graph theory, with applications to graph drawing and VLSI layout. No polynomial time constant approximation algorithm is known for this NP-complete problem. We prove that a natural approach to planar drawing of toroidal graphs (used already by Pach and T\'oth) gives a polynomial time constant approximation algorithm for the crossing number of toroidal graphs with bounded degree. In this proof we present a new ``grid'' theorem on toroidal graphs.
Česky
Dokážeme polynomiální aproximační algoritmus pro výpočet průsečíkového čísla toroidálních grafů s omezeným stupněm.
Návaznosti
| GA201/05/0050, projekt VaV |
|