On weighted sublinear separators
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On weighted sublinear separators
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/LL2005" target="_blank" >LL2005: Algorithms and Complexity within and beyond Bounded Expansion</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Graph Theory
ISSN
0364-9024
e-ISSN
1097-0118
Volume of the periodical
100
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
11
Pages from-to
270-280
UT code for WoS article
000721816200001
EID of the result in the Scopus database
2-s2.0-85119666720