On the complexity landscape of connected f-factor problems

DOI10.4230/LIPICS.MFCS.2016.41zbMATH Open1398.68233arXiv1812.02037MaRDI QIDQ4608602FDOQ4608602

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

Publication date: 21 March 2018

Full work available at URL: https://arxiv.org/abs/1812.02037

Recommendations

• On the complexity landscape of connected \(f\)-factor problems
• Vertex Exponential Algorithms for Connected f-Factors
• Approximation and exact algorithms for special cases of connected \(f\)-factors
• On the complexity of all \(( g , f )\)-factors problem
• Connected \((g,f)\)-factors

zbMATH Keywords

randomized algorithms\(f\)-factorsconnected \(f\)-factorsquasi-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)

Cited In (3)

• Approximation and exact algorithms for special cases of connected \(f\)-factors
• On the complexity landscape of connected \(f\)-factor problems
• Vertex Exponential Algorithms for Connected f-Factors

This page was built for publication: On the complexity landscape of connected \(f\)-factor problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608602)