On the Complexity Landscape of Connected f-Factor Problems
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On the Complexity Landscape of Connected f-Factor Problems
Original language description
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
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Algorithmica
ISSN
0178-4617
e-ISSN
—
Volume of the periodical
81
Issue of the periodical within the volume
6
Country of publishing house
US - UNITED STATES
Number of pages
27
Pages from-to
2606-2632
UT code for WoS article
000465544600015
EID of the result in the Scopus database
2-s2.0-85064917315