Optimal data reduction for graph coloring using low-degree polynomials
From MaRDI portal
Publication:5111881
DOI10.4230/LIPICS.IPEC.2017.22zbMATH Open1443.68132OpenAlexW2963300845MaRDI QIDQ5111881FDOQ5111881
Authors: Bart M. P. Jansen, Astrid Pieterse 
Publication date: 27 May 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.22
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Fundamentals of parameterized complexity
- Parameterized algorithms
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernelization of packing problems
- Data reduction for graph coloring problems
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Optimal sparsification for some binary CSPs using low-degree polynomials
- Fine-grained parameterized complexity analysis of graph coloring problems
Cited In (8)
- Optimal data reduction for graph coloring using low-degree polynomials
- Sparsification lower bounds for list \(H\)-coloring
- Data reduction for graph coloring problems
- Data reduction for graph coloring problems
- Best-case and worst-case sparsifiability of Boolean CSPs
- Polynomial-time data reduction for weighted problems beyond additive goal functions
- Best-case and worst-case sparsifiability of Boolean CSPs
- Constraint and satisfiability reasoning for graph coloring
This page was built for publication: Optimal data reduction for graph coloring using low-degree polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111881)
