Paired 2-disjoint path covers of burnt pancake graphs with faulty elements
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10477122" target="_blank" >RIV/00216208:11320/24:10477122 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mUAMPM6hvO" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mUAMPM6hvO</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2023.114327" target="_blank" >10.1016/j.tcs.2023.114327</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Paired 2-disjoint path covers of burnt pancake graphs with faulty elements
Popis výsledku v původním jazyce
The burnt pancake graph BPn is the Cayley graph of the hyperoctahedral group using prefix reversals as generators. Let {u,v} and {x,y} be any two pairs of distinct vertices of BPn for n>=4. We show that there are u-v and x-y paths whose vertices partition the vertex set of BPn even if BPn has up to n-4 faulty elements. On the other hand, for every n>=3 there is a set of n-2 faulty edges or faulty vertices for which such a fault-free disjoint path cover does not exist.
Název v anglickém jazyce
Paired 2-disjoint path covers of burnt pancake graphs with faulty elements
Popis výsledku anglicky
The burnt pancake graph BPn is the Cayley graph of the hyperoctahedral group using prefix reversals as generators. Let {u,v} and {x,y} be any two pairs of distinct vertices of BPn for n>=4. We show that there are u-v and x-y paths whose vertices partition the vertex set of BPn even if BPn has up to n-4 faulty elements. On the other hand, for every n>=3 there is a set of n-2 faulty edges or faulty vertices for which such a fault-free disjoint path cover does not exist.
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/GA19-08554S" target="_blank" >GA19-08554S: Struktury a algoritmy ve velmi symetrických grafech</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2024
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
1879-2294
Svazek periodika
986
Číslo periodika v rámci svazku
27 February 2024
Stát vydavatele periodika
NL - Nizozemsko
Počet stran výsledku
12
Strana od-do
1-12
Kód UT WoS článku
001160536900001
EID výsledku v databázi Scopus
2-s2.0-85179896294