Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Long paths in hypercubes with a quadratic number of faults

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00206366" target="_blank" >RIV/00216208:11320/09:00206366 - isvavai.cz</a>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Long paths in hypercubes with a quadratic number of faults

  • Popis výsledku v původním jazyce

    A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set of f faulty vertices is called long if its length is at least 2^n-2f-2. We present a function phi(n) = Theta(n^2) such that if f {= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n). Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f {= phi(n), the existence of a long fault-free pathbetween an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.

  • Název v anglickém jazyce

    Long paths in hypercubes with a quadratic number of faults

  • Popis výsledku anglicky

    A path between distinct vertices u and v of the n-dimensional hypercube Q(n) avoiding a given set of f faulty vertices is called long if its length is at least 2^n-2f-2. We present a function phi(n) = Theta(n^2) such that if f {= phi(n) then there is a long fault-free path between every pair of distinct vertices of the largest fault-free block of Q(n). Moreover, the bound provided by phi(n) is asymptotically optimal. Furthermore, we show that assuming f {= phi(n), the existence of a long fault-free pathbetween an arbitrary pair of vertices may be verified in polynomial time with respect to n and, if the path exists, its construction performed in linear time with respect to its length.

Klasifikace

  • Druh

    J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

  • CEP obor

    BA - Obecná matematika

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Ostatní

  • Rok uplatnění

    2009

  • 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

    Information Sciences

  • ISSN

    0020-0255

  • e-ISSN

  • Svazek periodika

    179

  • Číslo periodika v rámci svazku

    21

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    9

  • Strana od-do

  • Kód UT WoS článku

    000269753200003

  • EID výsledku v databázi Scopus