Cover Image

Many Flavors of Edit Distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bhattacharya, Sudatta, Dey, Sanjana, Goldenberg, Elazar, Koucký, Michal
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

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
by: Bhattacharya, Sudatta, et al.
Published: (2025)

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

SquareSort: a cache-oblivious sorting algorithm
by: Koucký, Michal, et al.
Published: (2024)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
by: Goldenberg, Elazar, et al.
Published: (2022)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

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

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

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

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

Approximate Circular Pattern Matching under Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

String Sanitization Under Edit Distance: Improved and Generalized
by: Mieno, Takuya, et al.
Published: (2020)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

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

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

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

Nearly Optimal List Labeling
by: Bender, Michael A., et al.
Published: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Improved Rank Aggregation under Fairness Constraint
by: Chakraborty, Diptarka, et al.
Published: (2025)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
by: Dey, Dipan, et al.
Published: (2024)

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
by: Dey, Dipan, et al.
Published: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
by: Haeupler, Bernhard, et al.
Published: (2026)

Exponent-Strings and Their Edit Distance
by: Baek, Ingyu
Published: (2024)

Perfect Matchings and Popularity in the Many-to-Many Setting
by: Kavitha, Telikepalli, et al.
Published: (2024)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

Text Indexing and Pattern Matching with Ephemeral Edits
by: Pissis, Solon P.
Published: (2025)

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

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

RSVP: Beyond Weisfeiler Lehman Graph Isomorphism Test
by: Dutta, Sourav, et al.
Published: (2024)

Improved Sublinear-time Moment Estimation using Weighted Sampling
by: Bhattacharya, Anup, et al.
Published: (2025)

Distributed Distance Sensitivity Oracles
by: Manoharan, Vignesh, et al.
Published: (2024)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

Low-Cost Arborescence Under Edge Faults
by: Dey, Dipan, et al.
Published: (2026)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
by: Pilipczuk, Michał, et al.
Published: (2025)

Losing Treewidth In The Presence Of Weights
by: Włodarczyk, Michał
Published: (2024)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
by: Opler, Michal
Published: (2024)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
by: Włodarczyk, Michał
Published: (2024)

Designing Compact ILPs via Fast Witness Verification
by: Włodarczyk, Michał
Published: (2025)