Imagen de Portada

On the Complexity of Finding Approximate LCS of Multiple Strings

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Hasibi, Hamed, Mhaskar, Neerja, Smyth, W. F.
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

String Covering: A Survey
por: Mhaskar, Neerja, et al.
Publicado: (2022)

Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
por: Dehghani, Hossein, et al.
Publicado: (2022)

V-Words, Lyndon Words and Galois Words
por: Daykin, Jacqueline W., et al.
Publicado: (2024)

Efficient Algorithms to Compute Closed Substrings
por: Jain, Samkith K, et al.
Publicado: (2025)

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

Subsequence Matching and LCS with Segment Number Constraints
por: Yonemoto, Yuki, et al.
Publicado: (2024)

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

Faster Space-Efficient STR-IC-LCS Computation
por: Yonemoto, Yuki, et al.
Publicado: (2022)

Linear-space LCS enumeration with quadratic-time delay for two strings
por: Sakai, Yoshifumi
Publicado: (2025)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
por: Li, Rao
Publicado: (2024)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
por: Dumitrescu, Adrian
Publicado: (2021)

On the Parallel Complexity of Finding a Matroid Basis
por: Khanna, Sanjeev, et al.
Publicado: (2025)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
por: Chang, Yi-Jun, et al.
Publicado: (2024)

Parameterized Complexity of Finding Dissimilar Shortest Paths
por: Funayama, Ryo, et al.
Publicado: (2024)

Improved Sparse Recovery for Approximate Matrix Multiplication
por: Uffenheimer, Yahel, et al.
Publicado: (2026)

Optimal Approximate Matrix Multiplication over Sliding Window
por: Xian, Haoming, et al.
Publicado: (2025)

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

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
por: Chen, Lin, et al.
Publicado: (2026)

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

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

Quantum Algorithm for the Multiple String Matching Problem
por: Khadiev, Kamil, et al.
Publicado: (2024)

Online String Attractors
por: Whittington, Philip
Publicado: (2024)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
por: Chen, Yong, et al.
Publicado: (2025)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
por: Friggstad, Zachary, et al.
Publicado: (2025)

Approximation and FPT Algorithms for Finding DM-Irreducible Spanning Subgraphs
por: Norose, Ryoma, et al.
Publicado: (2024)

Minimizers in Semi-Dynamic Strings
por: Zuba, Wiktor, et al.
Publicado: (2025)

Scalable Distributed String Sorting
por: Kurpicz, Florian, et al.
Publicado: (2024)

Pattern Discovery in Colored Strings
por: Lipták, Zsuzsanna, et al.
Publicado: (2020)

String Indexing with Compressed Patterns
por: Bille, Philip, et al.
Publicado: (2019)

Elastic-Degenerate String Comparison
por: Gabory, Esteban, et al.
Publicado: (2024)

Improved Approximation Algorithms for the Multiple-Depot Split Delivery Vehicle Routing Problem
por: Zhao, Jingyang, et al.
Publicado: (2026)

Computing String Covers in Sublinear Time
por: Radoszewski, Jakub, et al.
Publicado: (2024)

Algorithms for Parameterized String Matching with Mismatches
por: Saha, Apurba, et al.
Publicado: (2024)

A Textbook Solution for Dynamic Strings
por: Lipták, Zsuzsanna, et al.
Publicado: (2024)

Online Computation of String Net Frequency
por: Guo, Peaker, et al.
Publicado: (2024)

Sensitivity of Repetitiveness Measures to String Reversal
por: Bannai, Hideo, et al.
Publicado: (2026)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
por: Roditty, Liam, et al.
Publicado: (2025)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
por: Dempsey, Jordan, et al.
Publicado: (2024)

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

Generalization of Repetitiveness Measures for Two-Dimensional Strings
por: Carfagna, Lorenzo, et al.
Publicado: (2025)