Hypertree-depth and minors in hypergraphs
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10366924" target="_blank" >RIV/00216208:11320/12:10366924 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1016/j.tcs.2012.09.007" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.09.007</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2012.09.007" target="_blank" >10.1016/j.tcs.2012.09.007</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Hypertree-depth and minors in hypergraphs
Popis výsledku v původním jazyce
We introduce two new notions for hypergraphs, hypertree-depth and minors in hypergraphs. We characterise hypergraphs of bounded hypertree-depth by the ultramonotone robber and marshals game, by vertex-hyperrankings and by centred hypercolourings. Furthermore, we show that minors in hypergraphs are 'well-behaved' with respect to hypertree-depth and other hypergraph invariants, such as generalised hypertree-depth and generalised hyperpath-width. We work in the framework of hypergraph pairs (G, H), consisting of a graph G and a hypergraph H that share the same vertex set. This general framework allows us to obtain hypergraph minors, graph minors and induced graph minors as special cases.
Název v anglickém jazyce
Hypertree-depth and minors in hypergraphs
Popis výsledku anglicky
We introduce two new notions for hypergraphs, hypertree-depth and minors in hypergraphs. We characterise hypergraphs of bounded hypertree-depth by the ultramonotone robber and marshals game, by vertex-hyperrankings and by centred hypercolourings. Furthermore, we show that minors in hypergraphs are 'well-behaved' with respect to hypertree-depth and other hypergraph invariants, such as generalised hypertree-depth and generalised hyperpath-width. We work in the framework of hypergraph pairs (G, H), consisting of a graph G and a hypergraph H that share the same vertex set. This general framework allows us to obtain hypergraph minors, graph minors and induced graph minors as special cases.
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
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2012
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
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Svazek periodika
Neuveden
Číslo periodika v rámci svazku
463
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
12
Strana od-do
84-95
Kód UT WoS článku
000312181200008
EID výsledku v databázi Scopus
—