Additive sparsification of CSPs

DOI10.1145/3625824MaRDI QIDQ7023578zbMATH OpenFDO

Authors S. Zivny

Publication date 21 February 2025

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3625824

zbMATH Keywords

constraint satisfactionsparsification

Mathematics Subject Classification ID

Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A general framework for graph sparsification
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Additive spanners in nearly quadratic time
• Additive Sparsification of CSPs.
• All-Pairs Almost Shortest Paths
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Automata, Languages and Programming
• Bigraphs versus digraphs via matrices
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Complexity of network synchronization
• Extensions and limits to vertex sparsification
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Graph spanners
• Graph sparsification by effective resistances
• Graph Sparsification in the Semi-streaming Model
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• Near-additive spanners and near-exact hopsets, a unified view
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• New additive spanners
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• New constructions of \(({\alpha}, {\beta})\)-spanners and purely additive spanners
• New notions and constructions of sparsification for graphs and hypergraphs
• On multiplicative -approximations and some geometric applications
• On sketching quadratic forms
• On sparse spanners of weighted graphs
• Sketching cuts in graphs and hypergraphs
• Sparse Distance Preservers and Additive Spanners
• Sparsification of binary CSPs
• Sparsification of two-variable valued constraint satisfaction problems
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Spectral sparsification of graphs
• Spectral sparsification of hypergraphs
• Twice-Ramanujan sparsifiers

This page was built for publication: Additive sparsification of CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7023578)