On the complexity landscape of connected \(f\)-factor problems
From MaRDI portal
Publication:2414869
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
randomized algorithmsexponential time hypothesisconnected \(f\)-factorsNP-intermediatequasi-polynomial time algorithms
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
