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

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

M. S. Ramanujan, N. S. Narayanaswamy, Robert Ganian, Sebastian Ordyniak, 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 algorithmsexponential time hypothesisconnected \(f\)-factorsNP-intermediatequasi-polynomial time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rural postman parameterized by the number of components of required edges
• A short proof of the tree-packing theorem
• Graph factors and factorization: 1985--2003: a survey
• The complexity of regular subgraph recognition
• Matching theory
• Which problems have strongly exponential complexity?
• Approximation algorithms for connected graph factors of minimum weight
• Connected factors in graphs -- a survey
• Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
• Vertex Exponential Algorithms for Connected f-Factors
• Approximability of Connected Factors
• Approximation and Exact Algorithms for Special Cases of Connected f-Factors
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• Factors and factorizations of graphs—a survey
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Factorization of Linear Graphs
• The Factors of Graphs
• A Short Proof of the Factor Theorem for Finite Graphs