On weighted sublinear separators
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10448436" target="_blank" >RIV/00216208:11320/22:10448436 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=XwLX~yS7V0" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=XwLX~yS7V0</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/jgt.22777" target="_blank" >10.1002/jgt.22777</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On weighted sublinear separators
Popis výsledku v původním jazyce
Consider a graph (Formula presented.) with an assignment of costs to vertices. Even if (Formula presented.) and all its subgraphs admit balanced separators of sublinear size, (Formula presented.) may only admit a balanced separator of sublinear cost after deleting a small set (Formula presented.) of exceptional vertices. We improve the bound on (Formula presented.) from (Formula presented.) to (Formula presented.), for any fixed number of iterations of the logarithm.
Název v anglickém jazyce
On weighted sublinear separators
Popis výsledku anglicky
Consider a graph (Formula presented.) with an assignment of costs to vertices. Even if (Formula presented.) and all its subgraphs admit balanced separators of sublinear size, (Formula presented.) may only admit a balanced separator of sublinear cost after deleting a small set (Formula presented.) of exceptional vertices. We improve the bound on (Formula presented.) from (Formula presented.) to (Formula presented.), for any fixed number of iterations of the logarithm.
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/LL2005" target="_blank" >LL2005: Algoritmy a složitost v rámci a nad omezenou expanzí</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2022
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
Journal of Graph Theory
ISSN
0364-9024
e-ISSN
1097-0118
Svazek periodika
100
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
11
Strana od-do
270-280
Kód UT WoS článku
000721816200001
EID výsledku v databázi Scopus
2-s2.0-85119666720