J 2019

On the Complexity Landscape of Connected f-Factor Problems

GANIAN, Robert, N. S. NARAYANASWAMY, Sebastian ORDYNIAK, C. S. RAHUL, M. S. RAMANUJAN et. al.

Základní údaje

Originální název

On the Complexity Landscape of Connected f-Factor Problems

Autoři

GANIAN, Robert (203 Česká republika, garant, domácí), N. S. NARAYANASWAMY (356 Indie), Sebastian ORDYNIAK (276 Německo), C. S. RAHUL (356 Indie) a M. S. RAMANUJAN (356 Indie)

Vydání

Algorithmica, Springer, 2019, 0178-4617

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 0.650

Kód RIV

RIV/00216224:14330/19:00113716

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000465544600015

Klíčová slova anglicky

Parameterized Complexity
Změněno: 14. 5. 2020 10:41, Mgr. Michal Petr

Anotace

V originále

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