Sparsification and subexponential approximation

2016/10/12 by Édouard Bonnet, Vangélis Th. Paschos, Vangelis Th. Paschos · 1 citation
Computer Science · Mathematics · #Algorithm #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Cover (algebra) #Discrete mathematics #Dominating set #Error Correcting Code Techniques #Exponential function #Feedback vertex set #Graph #Independent set #Mathematics #Optimization and Search Problems #Order (exchange) #Set (abstract data type) #Set cover problem #Vertex (graph theory) #Vertex cover

paper · doi:10.1007/s00236-016-0281-2

crossref issued 2016/10/12 · crossref published 2016/10/12 · crossref published-online 2016/10/12 · openalex publication_date 2016/10/12 · crossref created 2016/10/12 · crossref published-print 2018/02/01 · crossref deposited 2018/02/01 · crossref indexed 2025/09/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Citations

• Invitation to Fixed-Parameter Algorithms
• Exponential-Time Approximation of Hard Problems
• Parameterized Complexity and Approximation Algorithms
• Which Problems Have Strongly Exponential Complexity?
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• Set Partitioning via Inclusion-Exclusion
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Proof verification and the hardness of approximation problems
• Fixed-Parameter and Approximation Algorithms: A New Look

Cited by

• Feedback arc set [wikipedia]