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) -> {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) -> {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