scientific article; zbMATH DE number 1256718
From MaRDI portal
Publication:4228453
zbMath0924.68150MaRDI QIDQ4228453
András A. Benczúr, David R. Karger
Publication date: 18 May 1999
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (37)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Graph coarsening: from scientific computing to machine learning ⋮ On computing minimum\((s,t)\)-cuts in digraphs ⋮ Recent developments in maximum flow algorithms ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Shape Simplification Through Graph Sparsification ⋮ Spectral sparsification in the semi-streaming setting ⋮ A Spectral Approach to Network Design ⋮ Sparsification of Binary CSPs ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Unnamed Item ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Intractability of min- and max-cut in streaming graphs ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Faster cut sparsification of weighted graphs ⋮ Vertex Sparsification in Trees ⋮ Drawing Big Graphs Using Spectral Sparsification ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ On percolation and ‐hardness ⋮ Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Ranking and Sparsifying a Connection Graph ⋮ Information graph flow: a geometric approximation of quantum and statistical systems ⋮ Correlation clustering in data streams ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Sparsification of Binary CSPs ⋮ A General Framework for Graph Sparsification ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Cutting Corners Cheaply, or How to Remove Steiner Points ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems
This page was built for publication:
