On the complexity landscape of connected \(f\)-factor problems

DOI10.1007/s00453-019-00546-zzbMath1422.68110MaRDI QIDQ2414869

Sebastian Ordyniak, M. S. Ramanujan, N. S. Narayanaswamy, Robert Ganian, C. S. Rahul

Publication date: 17 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00546-z

zbMATH Keywords

randomized algorithms; exponential time hypothesis; connected \(f\)-factors; NP-intermediate; quasi-polynomial time algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C40: Connectivity

68W20: Randomized algorithms