Best-Case and Worst-Case Sparsifiability of Boolean CSPs
Authors:
Open Access
- 10 January 2020
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 82 (8) , 2200-2242
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (024.002.003)
This publication has 19 references indexed in Scilit:
- Weak bases of Boolean co-clonesInformation Processing Letters, 2014
- On Sparsification for Computing TreewidthAlgorithmica, 2014
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy CollapsesJournal of the ACM, 2014
- Kernelization Lower Bounds by Cross-CompositionSIAM Journal on Discrete Mathematics, 2014
- Kernelization of Packing Problems2012
- Kernelization – Preprocessing with a Guarantee2012
- Kernel bounds for disjoint cycles and disjoint pathsTheoretical Computer Science, 2011
- A rendezvous of logic, complexity, and algebraACM SIGACT News, 2006
- Classifying the Complexity of Constraints Using Finite AlgebrasSIAM Journal on Computing, 2005
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer MatrixSIAM Journal on Computing, 1979