D
2009
Approximating the Crossing Number of Apex Graphs
HLINĚNÝ, Petr, Markus CHIMANI a Petra MUTZEL
Základní údaje
Originální název
Approximating the Crossing Number of Apex Graphs
Název česky
Aproximace průsečíkového čísla apexových grafů
Autoři
HLINĚNÝ, Petr (203 Česká republika, garant, domácí), Markus CHIMANI (276 Německo) a Petra MUTZEL (276 Německo)
Vydání
5417. vyd. Berlin, Symposium Graph Drawing 2008, Lecture Notes in Computer Science, od s. 432-434, 3 s. 2009
Nakladatel
Springer Verlag
Další údaje
Typ výsledku
Stať ve sborníku
Obor
10201 Computer sciences, information science, bioinformatics
Utajení
není předmětem státního či obchodního tajemství
Forma vydání
tištěná verze "print"
Impakt faktor
Impact factor: 0.402 v roce 2005
Kód RIV
RIV/00216224:14330/09:00065851
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
crossing number; crossing minimization; apex graph
Příznaky
Mezinárodní význam, Recenzováno
V originále
We show that the crossing number of an apex graph, i.e.\ a graph $G$ from which only one vertex $v$ has to be removed to make it planar, can be approximated up to a factor of $\Delta(G-v)\cdot d(v)/2$ by solving the \emph{vertex inserting} problem, i.e.\ inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Due to a recently developed polynomial algorithm for the latter problem, this establishes the first polynomial fixed-constant approximation algorithm for the crossing number problem of apex graphs with bounded degree.
Česky
Dokážeme, že průsečíkové číslo grafu G, který se jedním vrcholem v liší od rovinného, je aproximovatelné s faktorem \Delta(G-v)\cdot d(v)/2 problémem vložení vrcholu v do rovinného nakreslení G.
Návaznosti
GA201/08/0308, projekt VaV | Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti | Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti |
|
MSM0021622419, záměr | Název: Vysoce paralelní a distribuované výpočetní systémy | Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy |
|
1M0545, projekt VaV | Název: Institut Teoretické Informatiky | Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky |
|
Zobrazeno: 11. 11. 2024 04:36