SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F21%3A10437051" target="_blank" >RIV/00216208:11320/21:10437051 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8XLxDwODDY" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=8XLxDwODDY</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/20M1311156" target="_blank" >10.1137/20M1311156</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES
Popis výsledku v původním jazyce
We give a natural sufficient condition for an intersection graph of compact convex sets in R-d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.
Název v anglickém jazyce
SUBLINEAR SEPARATORS IN INTERSECTION GRAPHS OF CONVEX SHAPES
Popis výsledku anglicky
We give a natural sufficient condition for an intersection graph of compact convex sets in R-d to have a balanced separator of sublinear size. This condition generalizes several previous results on sublinear separators in intersection graphs. Furthermore, the argument used to prove the existence of sublinear separators is based on a connection with generalized coloring numbers which has not been previously explored in geometric settings.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA17-04611S" target="_blank" >GA17-04611S: Ramseyovské aspekty barvení grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2021
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Svazek periodika
35
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
16
Strana od-do
1149-1164
Kód UT WoS článku
000674142200026
EID výsledku v databázi Scopus
2-s2.0-85108682562