:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Kyng, Rasmus, Meierhans, Simon, Zöcklein, Gernot
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2408.11375
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Simple Dynamic Spanner via APSP
by: Kyng, Rasmus, et al.
Published: (2024)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Dynamic Hierarchical $j$-Tree Decomposition and Its Applications
by: Goranci, Gramoz, et al.
Published: (2026)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
by: Grunau, Christoph, et al.
Published: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
by: Kyng, Rasmus, et al.
Published: (2025)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
by: Adil, Deeksha, et al.
Published: (2024)

Optimal Electrical Oblivious Routing on Expanders
by: Florescu, Cella, et al.
Published: (2024)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Improved Additive Approximation Algorithms for APSP
by: Jin, Ce, et al.
Published: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
by: Koo, Jaehyun
Published: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Fully Dynamic Spectral Sparsification of Hypergraphs
by: Goranci, Gramoz, et al.
Published: (2025)

Iterative Refinement for $\ell_p$-norm Regression
by: Adil, Deeksha, et al.
Published: (2019)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
by: Roditty, Liam, et al.
Published: (2025)

Fully Dynamic Spectral Sparsification for Directed Hypergraphs
by: Forster, Sebastian, et al.
Published: (2025)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
by: Gottesbüren, Lars, et al.
Published: (2025)

Message Optimality and Message-Time Trade-offs for APSP and Beyond
by: Dufoulon, Fabien, et al.
Published: (2025)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Max-Distance Sparsification for Diversification and Clustering
by: Kumabe, Soh
Published: (2024)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

Efficient Algorithms and New Characterizations for CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2024)

Eulerian Graph Sparsification by Effective Resistance Decomposition
by: Jambulapati, Arun, et al.
Published: (2024)

Balancing Weights, Directed Sparsification, and Augmenting Paths
by: Li, Jason
Published: (2026)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
by: Kenneth, Yotam, et al.
Published: (2023)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

Fast and Faithful Edge Bundling using Spectral Sparsification
by: Jiang, Xingjue, et al.
Published: (2026)

Additive Sparsification of CSPs
by: Pelleg, Eden, et al.
Published: (2021)

Spectral Sparsification by Deterministic Discrepancy Walk
by: Lau, Lap Chi, et al.
Published: (2024)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Adaptive Sparsification for Linear Programming
by: Objois, Étienne, et al.
Published: (2025)

Quantum Speedup for Hypergraph Sparsification
by: Liu, Chenghua, et al.
Published: (2025)