Clique Cover and Graph Separation: New Incompressibility Results
- 1 January 2012
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 254-265
Abstract
No abstract availableKeywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Kernelization of Packing Problems2012
- Clique Cover and Graph Separation: New Incompressibility ResultsLecture Notes in Computer Science, 2012
- Infeasibility of instance compression and succinct PCPs for NPJournal of Computer and System Sciences, 2011
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses2010
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic ApplicationsSIAM Journal on Computing, 2010
- On problems without polynomial kernelsJournal of Computer and System Sciences, 2009
- Kernelization: New Upper and Lower Bound Techniques2009
- Invitation to data reduction and problem kernelizationACM SIGACT News, 2007
- Competing provers yield improved Karp–Lipton collapse resultsInformation and Computation, 2005
- Some consequences of non-uniform conditions on uniform classesTheoretical Computer Science, 1983