Cover Image

Simple Linear-Size Additive Emulators

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Hoppenworth, Gary
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

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

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

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
by: Hoppenworth, Gary, et al.
Published: (2025)

New Separations and Reductions for Directed Preservers and Hopsets
by: Hoppenworth, Gary, et al.
Published: (2024)

Covering Approximate Shortest Paths with DAGs
by: Assadi, Sepehr, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

Simple Linear-time Repetition Factorization
by: Yonemoto, Yuki, et al.
Published: (2024)

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

Faster Linear-Size And-Or Path and Adder Circuits
by: Brenner, Ulrich, et al.
Published: (2024)

Path-Reporting Distance Oracles with Linear Size
by: Neiman, Ofer, et al.
Published: (2024)

Reviving Thorup's Shortcut Conjecture
by: Bernstein, Aaron, et al.
Published: (2025)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
by: Chanda, Debarshi
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

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

Low-Step Multi-Commodity Flow Emulators
by: Haeupler, Bernhard, et al.
Published: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

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

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

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

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

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Partition-based Simple Heaps
by: Brodal, Gerth Stølting, et al.
Published: (2026)

Additive Approximation Schemes for Low-Dimensional Embeddings
by: Anderson, Prashanti, et al.
Published: (2025)

Lawler-Moore Speedups via Additive Combinatorics
by: Bringmann, Karl, et al.
Published: (2026)

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

Simple Realizability of Abstract Topological Graphs
by: Da Lozzo, Giordano, et al.
Published: (2024)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

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

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

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

A Simple Algorithm for Clustering Discrete Distributions
by: Mitra, Pradipta
Published: (2026)

A Simple Algorithm for Dynamic Carpooling with Recourse
by: Efron, Yuval, et al.
Published: (2024)

A Simple Analysis of Ranking in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Noisy (Binary) Searching: Simple, Fast and Correct
by: Dereniowski, Dariusz, et al.
Published: (2021)

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

Simple and Optimal Sublinear Algorithms for Mean Estimation
by: Bertolotti, Beatrice, et al.
Published: (2024)