Sublinear time hypergraph sparsification via cut and edge sampling queries

DOI10.4230/LIPICS.ICALP.2021.53MaRDI QIDQ7241151zbMATH OpenFDO

Authors Yu Chen, Sanjeev Khanna

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.53

zbMATH Keywords

cut queriesgraph sparsificationhypergraphs

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A faster cutting plane method and its implications for combinatorial and convex optimization
• A general framework for graph sparsification
• An SDP-based algorithm for linear-sized spectral sparsification
• Cheeger inequalities for submodular transformations
• Fast and Space Efficient Spectral Sparsification in Dynamic Streams
• Graph sparsification by effective resistances
• Graph Sparsification in the Semi-streaming Model
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 1256718 (Why is no real title available?)
• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Minimum cuts and sparsification in hypergraphs
• Near-linear size hypergraph cut sparsifiers
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• New notions and constructions of sparsification for graphs and hypergraphs
• Random sampling in cut, flow, and network design problems
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Single pass spectral sparsification in dynamic streams
• Sketching cuts in graphs and hypergraphs
• Spectral sparsification in dynamic graph streams
• Spectral sparsification of hypergraphs
• Twice-Ramanujan sparsifiers

This page was built for publication: Sublinear time hypergraph sparsification via cut and edge sampling queries

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