Cover Image

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nogler, Jakob, Polak, Adam, Saha, Barna, Williams, Virginia Vassilevska, Xu, Yinzhan, Ye, Christopher
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hardness of Dynamic Tree Edit Distance and Friends
by: Hu, Bingbing, et al.
Published: (2025)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
by: Nogler, Jakob, et al.
Published: (2026)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
by: Saha, Barna, et al.
Published: (2024)

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

All-Hops Shortest Paths
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
by: Dalirrooyfard, Mina, et al.
Published: (2023)

More Asymmetry Yields Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

The Communication Complexity of Pattern Matching with Edits Revisited
by: Kociumaka, Tomasz, et al.
Published: (2026)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
by: Kociumaka, Tomasz, et al.
Published: (2014)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

A Refined Laser Method and Faster Matrix Multiplication
by: Alman, Josh, et al.
Published: (2020)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Listing 6-Cycles in Sparse Graphs
by: Williams, Virginia Vassilevska, et al.
Published: (2024)

Shortest Paths in Multimode Graphs
by: Kirkpatrick, Yael, et al.
Published: (2025)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)

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

Faster Cycle Detection in the Congested Clique
by: Censor-Hillel, Keren, et al.
Published: (2024)

All-Pairs Shortest Paths with Few Weights per Node
by: Abboud, Amir, et al.
Published: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
by: Black, Hadley, et al.
Published: (2025)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

Fast Approximate Counting of Cycles
by: Censor-Hillel, Keren, et al.
Published: (2024)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
by: Censor-Hillel, Keren, et al.
Published: (2025)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Pattern Matching under Weighted Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
by: Kirkpatrick, Yael, et al.
Published: (2026)

Beyond 2-approximation for k-Center in Graphs
by: Jin, Ce, et al.
Published: (2025)

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

Bootstrapping Dynamic APSP via Sparsification
by: Kyng, Rasmus, et al.
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)

Detecting Disjoint Shortest Paths in Linear Time and More
by: Akmal, Shyan, et al.
Published: (2024)

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

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
by: Kociumaka, Tomasz, et al.
Published: (2024)

On the Communication Complexity of Approximate Pattern Matching
by: Kociumaka, Tomasz, et al.
Published: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

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