Cover Image

Approximate Cartesian Tree Matching with One Difference

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Auvray, Bastien, David, Julien, Ghazawi, Samah, Groult, Richard, Landau, Gad M., Lecroq, Thierry
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximate Cartesian Tree Matching: an Approach Using Swaps
by: Auvray, Bastien, et al.
Published: (2023)

Cartesian Forest Matching
by: Auvray, Bastien, et al.
Published: (2025)

A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
by: Lecroq, Thierry
Published: (2024)

Approximate Cartesian Tree Matching with Substitutions
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

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

Efficient Computation of Periods and Covers Using Sampling
by: Lecroq, Thierry, et al.
Published: (2024)

Stringology-Based Motif Discovery from EEG Signals: an ADHD Case Study
by: Dahan, Anat, et al.
Published: (2026)

Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
by: Osterkamp, Eric M., et al.
Published: (2024)

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

25 Additional Problems -- Extension to the Book "125 Problems in Text Algorithms"
by: Crochemore, Maxime, et al.
Published: (2025)

Approximate Circular Pattern Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2022)

Approximate Bipartite $b$-Matching using Multiplicative Auction
by: Samineni, Bhargav, et al.
Published: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

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

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
by: Liu, Yang P.
Published: (2024)

Additive One Approximation for Minimum Degree Spanning Tree: Breaking the $O(mn)$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2026)

Approximate Spanning Tree Counting from Uncorrelated Edge Sets
by: Liu, Yang P., et al.
Published: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
by: Bhattacharya, Sayan, et al.
Published: (2023)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
by: Davies-Peck, Peter
Published: (2026)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Designing Approximate Binary Trees for Trees
by: Kellerhals, Leon, et al.
Published: (2026)

Entrywise Approximate Laplacian Solving
by: Chen, Jingbang, et al.
Published: (2024)

Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All
by: Panda, Atasi, et al.
Published: (2022)

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

Consistent Low-Rank Approximation
by: Woodruff, David P., et al.
Published: (2026)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
by: Buhrman, Harry, et al.
Published: (2025)

Catalytic Tree Evaluation From Matching Vectors
by: Henzinger, Alexandra, et al.
Published: (2026)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

Course Allocation with Credits via Stable Matching
by: Rodríguez, José, et al.
Published: (2025)

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

Budget and Profit Approximations for Spanning Tree Interdiction
by: Ostrovsky, Rafail, et al.
Published: (2025)

Tight Sampling Bounds for Eigenvalue Approximation
by: Swartworth, William, et al.
Published: (2024)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

Approximating the Top Eigenvector in Random Order Streams
by: Kacham, Praneeth, et al.
Published: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Faster Algorithms for Schatten-p Low Rank Approximation
by: Kacham, Praneeth, et al.
Published: (2024)

Prize-Collecting Steiner Tree: A 1.79 Approximation
by: Ahmadi, Ali, et al.
Published: (2024)