Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT

DOI10.4230/LIPIcs.IPEC.2015.163zbMath1372.68128arXiv1509.07437OpenAlexW2540110070MaRDI QIDQ5363770

Astrid Pieterse, Bart M. P. Jansen

Publication date: 29 September 2017

Full work available at URL: https://arxiv.org/abs/1509.07437

zbMATH Keywords

graph coloringHamiltonian cyclesatisfiabilitysparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Paths to Trees and Cacti ⋮ Paths to trees and cacti ⋮ Triangle packing in (sparse) tournaments: approximation and kernelization ⋮ Parameterized complexity of maximum edge colorable subgraph

This page was built for publication: Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT