2010
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
HLINĚNÝ, Petr a Markus CHIMANIZákladní údaje
Originální název
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
Název česky
Aproximace průsečíkového čísla grafů nakreslitelných na orientovaných plochách
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Markus CHIMANI (276 Německo)
Vydání
USA, internet, ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), od s. 918-927, 10 s. 2010
Nakladatel
SIAM / ACM
Další údaje
Jazyk
angličtina
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Spojené státy
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
elektronická verze "online"
Odkazy
Kód RIV
RIV/00216224:14330/10:00043102
Organizační jednotka
Fakulta informatiky
ISBN
978-0-89871-698-6
UT WoS
000280699900074
Klíčová slova anglicky
crossing number; crossing minimization; surface
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 4. 2. 2013 12:21, prof. RNDr. Petr Hliněný, Ph.D.
V originále
The crossing number of a graph is the least number of pairwise edge crossings in a drawing of the graph in the plane. We provide an $O(n\log n)$ time constant factor approximation algorithm for the crossing number of a graph of bounded maximum degree which is ``densely enough'' embeddable in an arbitrary fixed orientable surface.
Česky
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.
Návaznosti
| GA201/08/0308, projekt VaV |
| ||
| MSM0021622419, záměr |
| ||
| 1M0545, projekt VaV |
|