Sparsification of Two-Variable Valued Constraint Satisfaction Problems
From MaRDI portal
Publication:5270406
DOI10.1137/15M1046186zbMath1371.68112arXiv1509.01844MaRDI QIDQ5270406
Robert Krauthgamer, Arnold Filtser
Publication date: 23 June 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.01844
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (3)
Sparsification of Binary CSPs ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Sparsification of Binary CSPs
Cites Work
- Unnamed Item
- On Sketching Quadratic Forms
- Spectral sparsification via random spanners
- On Multiplicative $\lambda$-Approximations and Some Geometric Applications
- Sketching Cuts in Graphs and Hypergraphs
- Spectral Sparsification of Graphs
- Random sampling in residual graphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Graph Sparsification in the Semi-streaming Model
- Bigraphs versus digraphs via matrices
- Sparse Sums of Positive Semidefinite Matrices
- Twice-Ramanujan Sparsifiers
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- A general framework for graph sparsification
- Graph Sparsification by Effective Resistances
This page was built for publication: Sparsification of Two-Variable Valued Constraint Satisfaction Problems
