Imagen de Portada

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Ghaffari, Mohsen, Koo, Jaehyun
Formato:	Preprint
Publicado:	2025
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

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

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

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
por: Koo, Jaehyun
Publicado: (2024)

Parallel Dynamic Maximal Matching
por: Ghaffari, Mohsen, et al.
Publicado: (2024)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
por: Ghaffari, Mohsen, et al.
Publicado: (2024)

Density-Dependent Graph Orientation and Coloring in Scalable MPC
por: Ghaffari, Mohsen, et al.
Publicado: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
por: Chuzhoy, Julia, et al.
Publicado: (2026)

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

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
por: Ghaffari, Mohsen, et al.
Publicado: (2025)

Routing-Controlled Spanners
por: Grigorescu, Elena, et al.
Publicado: (2024)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
por: Dai, Jiangqi, et al.
Publicado: (2025)

UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees
por: De Man, Quinten, et al.
Publicado: (2026)

Directed Buy-at-Bulk Spanners
por: Grigorescu, Elena, et al.
Publicado: (2024)

New Greedy Spanners and Applications
por: Popova, Elizaveta, et al.
Publicado: (2026)

Multiplicative Spanners in Minor-Free Graphs
por: Bodwin, Greg, et al.
Publicado: (2025)

Approximate Light Spanners in Planar Graphs
por: Le, Hung, et al.
Publicado: (2025)

Shortcuts and Transitive-Closure Spanners Approximation
por: Chalermsook, Parinya, et al.
Publicado: (2025)

Minimum Temporal Spanners in Happy Graphs
por: Casteigts, Arnaud, et al.
Publicado: (2026)

Almost-Optimal Sublinear Additive Spanners
por: Tan, Zihan, et al.
Publicado: (2023)

Graph Spanners for Group Steiner Distances
por: Bilò, Davide, et al.
Publicado: (2024)

A Unified Framework for Hopsets and Spanners
por: Neiman, Ofer, et al.
Publicado: (2021)

Dynamic Light Spanners in Doubling Metrics
por: Bhore, Sujoy, et al.
Publicado: (2026)

Longest Common Extension of a Dynamic String in Parallel Constant Time
por: Albert, Daniel
Publicado: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
por: He, Jialin, et al.
Publicado: (2025)

Greedy Completion for Weighted $(α,β)$-Spanners
por: Tzalik, Elad
Publicado: (2026)

Lightweight Near-Additive Spanners
por: Gitlitz, Yuval, et al.
Publicado: (2024)

Finding 4-Additive Spanners: Faster, Stronger, and Simpler
por: Qi, Chuhan
Publicado: (2025)

A Lower Bound for Light Spanners in General Graphs
por: Bodwin, Greg, et al.
Publicado: (2024)

Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
por: Ahmed, Reyan, et al.
Publicado: (2024)

Faster Parallel Batch-Dynamic Algorithms for Low Out-Degree Orientation
por: Blelloch, Guy, et al.
Publicado: (2026)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
por: Bodwin, Greg, et al.
Publicado: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
por: Parter, Merav, et al.
Publicado: (2024)

The Complexity of Geodesic Spanners
por: de Berg, Sarita, et al.
Publicado: (2023)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
por: Bhore, Sujoy, et al.
Publicado: (2024)

Algorithmic Extensions of Dirac's Theorem
por: Fomin, Fedor V., et al.
Publicado: (2020)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
por: Ghaffari, Mohsen, et al.
Publicado: (2024)

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

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
por: Dalirrooyfard, Mina, et al.
Publicado: (2024)

Parallel Batch-Dynamic Maximal Independent Set
por: Blelloch, Guy, et al.
Publicado: (2026)