Cover Image

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dudek, Bartłomiej, Gawrychowski, Paweł, Starikovskaya, Tatiana
Format:	Preprint
Published:	2020
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

Streaming periodicity with mismatches, wildcards, and edits
by: Ghazi, Taha El, et al.
Published: (2025)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Pattern Matching with Mismatches and Wildcards
by: Bathie, Gabriel, et al.
Published: (2024)

Internal Pattern Matching in Small Space and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
by: Bathie, Gabriel, et al.
Published: (2024)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
by: Bathie, Gabriel, et al.
Published: (2023)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
by: Gawrychowski, Paweł, et al.
Published: (2024)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Balancing Two-Dimensional Straight-Line Programs
by: Boneh, Itai, et al.
Published: (2025)

Longest Common Extensions with Wildcards: Trade-off and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
by: Gawrychowski, Pawel, et al.
Published: (2024)

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
by: Dudek, Bartłomiej, et al.
Published: (2026)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Equivalence Testing: The Power of Bounded Adaptivity
by: Chakraborty, Diptarka, et al.
Published: (2024)

Fault-Equivalent Lowest Common Ancestors
by: Petruschka, Asaf
Published: (2024)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
by: Tsujimoto, Taketo, et al.
Published: (2024)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

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

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

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

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
by: Adar, Tomer, et al.
Published: (2024)

A $(5/3+ε)$-Approximation for Tricolored Non-crossing Euclidean TSP
by: Baligács, Júlia, et al.
Published: (2024)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
by: Kanellopoulos, Sotiris, et al.
Published: (2026)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
by: Sharma, Vidya Sagar
Published: (2023)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree
by: Brown, Russell A.
Published: (2024)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
by: Bringmann, Karl, et al.
Published: (2026)