Imagen de Portada

Bootstrapping Dynamic APSP via Sparsification

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Kyng, Rasmus, Meierhans, Simon, Zöcklein, Gernot
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Max-Distance Sparsification for Diversification and Clustering
por: Kumabe, Soh
Publicado: (2024)

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

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

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

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

Balancing Weights, Directed Sparsification, and Augmenting Paths
por: Li, Jason
Publicado: (2026)

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

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

Stochastic Matching via Local Sparsification
por: Ahmadian, Sara, et al.
Publicado: (2026)

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

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

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

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

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

Additive Sparsification of CSPs
por: Pelleg, Eden, et al.
Publicado: (2021)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
por: Aamand, Anders, et al.
Publicado: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
por: Assadi, Sepehr, et al.
Publicado: (2025)

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