Cover Image

Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Das, Syamantak, Kumar, Nikhil, Vaz, Daniel
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Bounds for Sparsifying Random CSPs
by: Brakensiek, Joshua, et al.
Published: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
by: Chen, Yu, et al.
Published: (2024)

Improved Tree Sparsifiers in Near-Linear Time
by: Agassy, Daniel, et al.
Published: (2025)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

Twice-Ramanujan Sparsifiers
by: Batson, Joshua, et al.
Published: (2008)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

Nearly Tight Bounds for the Online Sorting Problem
by: Azar, Yossi, et al.
Published: (2025)

Dynamic Kernel Graph Sparsifiers
by: Cao, Yang, et al.
Published: (2022)

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Sparsifying Cayley Graphs on Every Group
by: Hsieh, Jun-Ting, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs
by: Zhao, Yibin
Published: (2025)

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Nearly Tight Bounds on Testing of Metric Properties
by: Bao, Yiqiao, et al.
Published: (2024)

Tight Bounds for Sorting Under Partial Information
by: van der Hoog, Ivor, et al.
Published: (2024)

Nearly-Tight Bounds for Zonotope Containment and Beyond
by: Eisenbrand, Friedrich, et al.
Published: (2026)

Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
by: Geng, Yutong, et al.
Published: (2025)

Counting Small Balanced (p,q)-bicliques in Signed Bipartite Graphs
by: Kiran, Mekala, et al.
Published: (2026)

Biclique Reconfiguration in Bipartite Graphs
by: Otachi, Yota, et al.
Published: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Private Geometric Median in Nearly-Linear Time
by: Kumar, Syamantak, et al.
Published: (2025)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Tight Bounds for Classical Open Addressing
by: Bender, Michael A., et al.
Published: (2024)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
by: van der Hoog, Ivor, et al.
Published: (2025)

Efficient Kernelization Algorithm for Bipartite Graph Matching
by: Wu, Guang, et al.
Published: (2024)

Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
by: Björklund, Andreas, et al.
Published: (2023)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
by: Anand, Aditya, et al.
Published: (2025)

Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
by: Chua, Lynn, et al.
Published: (2026)

Simplified Tight Bounds for Monotone Minimal Perfect Hashing
by: Kosolobov, Dmitry
Published: (2024)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
by: Kuszmaul, William, et al.
Published: (2024)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

A Tight Bound on Localization of Electrical Flows
by: Gurel-Gurevich, Ori, et al.
Published: (2026)