scientific article; zbMATH DE number 7053263
From MaRDI portal
Publication:5743382
zbMath1423.68216arXiv1107.3704MaRDI QIDQ5743382
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1107.3704
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Generalized Ramsey theory (05C55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
New Limits to Classical and Quantum Instance Compression ⋮ AND-compression of NP-complete problems: streamlined proof and minor observations ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ A completeness theory for polynomial (Turing) kernelization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- A new upper bound for diagonal Ramsey numbers
- Some consequences of non-uniform conditions on uniform classes
- On problems without polynomial kernels
- Ramsey's theorem - a new lower bound
- Parameterized complexity of finding subgraphs with hereditary properties.
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- Preprocessing of Min Ones Problems: A Dichotomy
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- (Meta) Kernelization
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- Bidimensionality and Geometric Graphs
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
This page was built for publication:
