Informace o publikaci
On the Complexity Landscape of Connected f-Factor Problems
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Algorithmica |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | https://doi.org/10.1007/s00453-019-00546-z |
| Doi | http://dx.doi.org/10.1007/s00453-019-00546-z |
| Klíčová slova | Parameterized Complexity |
| Popis | 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 |