Buchumschlag

Cut Sparsification and Succinct Representation of Submodular Hypergraphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kenneth, Yotam, Krauthgamer, Robert
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Cut-Query Algorithms with Few Rounds
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Sketching Cuts in Graphs and Hypergraphs
von: Kogan, Dmitry, et al.
Veröffentlicht: (2014)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Faster Pseudo-Deterministic Minimum Cut
von: Kenneth-Mordoch, Yotam
Veröffentlicht: (2026)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Fully Dynamic Spectral Sparsification of Hypergraphs
von: Goranci, Gramoz, et al.
Veröffentlicht: (2025)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
von: Forster, Sebastian, et al.
Veröffentlicht: (2025)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
von: Buchbinder, Niv, et al.
Veröffentlicht: (2025)

Succinct Graph Representations and Algorithmic Applications
von: Ullah, Ahammed, et al.
Veröffentlicht: (2026)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
von: Cheng, Yu, et al.
Veröffentlicht: (2024)

Stable coresets: Unleashing the power of uniform sampling
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

Quantum Speedup for Hypergraph Sparsification
von: Liu, Chenghua, et al.
Veröffentlicht: (2025)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
von: Balakrishnan, Girish, et al.
Veröffentlicht: (2023)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2025)

On Solving Linear Systems in Sublinear Time
von: Andoni, Alexandr, et al.
Veröffentlicht: (2018)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
von: Chhabra, Adil, et al.
Veröffentlicht: (2025)

Succinct Data Structures for Segments
von: Bille, Philip, et al.
Veröffentlicht: (2024)

Cuts and Gauges for Submodular Width
von: Lanzinger, Matthias
Veröffentlicht: (2026)

On the Adversarial Robustness of Online Importance Sampling
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Succinct Planar Encoding with Minor Operations
von: Kammer, Frank, et al.
Veröffentlicht: (2023)

Moderate Dimension Reduction for $k$-Center Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2023)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

SPIDER: Improved Succinct Rank and Select Performance
von: Laws, Matthew D., et al.
Veröffentlicht: (2024)

Succinct Data Structures for Baxter Permutation and Related Families
von: Chakraborty, Sankardeep, et al.
Veröffentlicht: (2024)

Coresets for Kernel Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2021)

Near-Optimal Dimension Reduction for Facility Location
von: Huang, Lingxiao, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Geometric Steiner Forest
von: Czumaj, Artur, et al.
Veröffentlicht: (2020)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
von: Balakrishnan, Girish, et al.
Veröffentlicht: (2024)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
von: Ferragina, Paolo, et al.
Veröffentlicht: (2025)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
von: Kuszmaul, William, et al.
Veröffentlicht: (2025)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
von: Hammer, Nina, et al.
Veröffentlicht: (2022)

Spectral Sparsification by Deterministic Discrepancy Walk
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Fast Nearest Neighbor Search for $\ell_p$ Metrics
von: Krauthgamer, Robert, et al.
Veröffentlicht: (2026)

Dimension Reduction for Clustering: The Curious Case of Discrete Centers
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2025)

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
von: Elberfeld, Michael, et al.
Veröffentlicht: (2025)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)