Fractional covers and matchings in families of weighted d-intervals
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F17%3A43932807" target="_blank" >RIV/49777513:23520/17:43932807 - isvavai.cz</a>
Výsledek na webu
<a href="https://link.springer.com/article/10.1007%2Fs00493-016-3174-7" target="_blank" >https://link.springer.com/article/10.1007%2Fs00493-016-3174-7</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00493-016-3174-7" target="_blank" >10.1007/s00493-016-3174-7</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Fractional covers and matchings in families of weighted d-intervals
Popis výsledku v původním jazyce
A d-interval is a union of at most d disjoint closed intervals on a fixed line. Tardos [Combinatorica 15 (1995), 123-134] and the second author [Disc. Comput. Geom. 18 (1997), 195-203] used topological tools to bound the transversal number τ of a family H of d-intervals in terms of d and the matching number ν of H. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both the topological method and an approach of Alon [Disc. Comput. Geom. 19 (1998), 333-334]. For the use of the latter, we prove a weighted version of Turan's theorem. We also provide a proof of the second author's upper bound that is more direct than the original proof.
Název v anglickém jazyce
Fractional covers and matchings in families of weighted d-intervals
Popis výsledku anglicky
A d-interval is a union of at most d disjoint closed intervals on a fixed line. Tardos [Combinatorica 15 (1995), 123-134] and the second author [Disc. Comput. Geom. 18 (1997), 195-203] used topological tools to bound the transversal number τ of a family H of d-intervals in terms of d and the matching number ν of H. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both the topological method and an approach of Alon [Disc. Comput. Geom. 19 (1998), 333-334]. For the use of the latter, we prove a weighted version of Turan's theorem. We also provide a proof of the second author's upper bound that is more direct than the original proof.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/GA14-19503S" target="_blank" >GA14-19503S: Barevnost a struktura grafů</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2017
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
COMBINATORICA
ISSN
0209-9683
e-ISSN
—
Svazek periodika
37
Číslo periodika v rámci svazku
4
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
18
Strana od-do
555-572
Kód UT WoS článku
000410055400001
EID výsledku v databázi Scopus
2-s2.0-84981237564