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”

On the Complexity Landscape of Connected f-Factor Problems

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00113716" target="_blank" >RIV/00216224:14330/19:00113716 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://doi.org/10.1007/s00453-019-00546-z" target="_blank" >https://doi.org/10.1007/s00453-019-00546-z</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1007/s00453-019-00546-z" target="_blank" >10.1007/s00453-019-00546-z</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    On the Complexity Landscape of Connected f-Factor Problems

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

    Let G be an undirected simple graph having n vertices and let f:V(G) -&gt; {0,…,n-1} be a function. An f-factor of G is a spanning subgraph H such that dH(v)=f(v) for every vertex v in V(G). The subgraph H is called a connected f-factor if, in addition, H is connected. A classical result of Tutte (Can J Math 6(1954):347–352, 1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connectedf-factor is easily seen to generalize HAMILTONIAN CYCLE and hence is NP-complete. In fact, the CONNECTED f-FACTOR problem remains NP-complete even when we restrict f(v) to be at least n^e for each vertex v and constant 0

  • Název v anglickém jazyce

    On the Complexity Landscape of Connected f-Factor Problems

  • Popis výsledku anglicky

    Let G be an undirected simple graph having n vertices and let f:V(G) -&gt; {0,…,n-1} be a function. An f-factor of G is a spanning subgraph H such that dH(v)=f(v) for every vertex v in V(G). The subgraph H is called a connected f-factor if, in addition, H is connected. A classical result of Tutte (Can J Math 6(1954):347–352, 1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connectedf-factor is easily seen to generalize HAMILTONIAN CYCLE and hence is NP-complete. In fact, the CONNECTED f-FACTOR problem remains NP-complete even when we restrict f(v) to be at least n^e for each vertex v and constant 0

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

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2019

  • 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

    Algorithmica

  • ISSN

    0178-4617

  • e-ISSN

  • Svazek periodika

    81

  • Číslo periodika v rámci svazku

    6

  • Stát vydavatele periodika

    US - Spojené státy americké

  • Počet stran výsledku

    27

  • Strana od-do

    2606-2632

  • Kód UT WoS článku

    000465544600015

  • EID výsledku v databázi Scopus

    2-s2.0-85064917315