Cover Image

Approximate Cartesian Tree Matching: an Approach Using Swaps

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Auvray, Bastien, David, Julien, Groult, Richard, Lecroq, Thierry
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

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

Approximate Cartesian Tree Matching with One Difference
by: Auvray, Bastien, et al.
Published: (2025)

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

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)

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

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

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

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

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

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

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)

Sequentially Swapping Tokens: Further on Graph Classes
by: Kiya, Hironori, et al.
Published: (2022)

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)

Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
by: Rohwedder, Lars, et al.
Published: (2024)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

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)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
by: Brinkop, Hauke, et al.
Published: (2025)

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

Randomized Rounding Approaches to Online Allocation, Sequencing, and Matching
by: Ma, Will
Published: (2024)

A New Approach for Approximating Directed Rooted Networks
by: Cohen, Sarel, et al.
Published: (2024)

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

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)

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)

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

Approximating Traveling Salesman Problems Using a Bridge Lemma
by: Böhm, Martin, et al.
Published: (2024)

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

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

The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach
by: Rahat, Md. Tanzeem, et al.
Published: (2025)