Image de couverture de livre

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Manea, Florin, Richardsen, Jonas, Schmid, Markus L.
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Linear Time Subsequence and Supersequence Regex Matching
par: Amarilli, Antoine, et autres
Publié: (2025)

Subsequences in Bounded Ranges: Matching and Analysis Problems
par: Kosche, Maria, et autres
Publié: (2022)

Absent Subsequences in Words
par: Kosche, Maria, et autres
Publié: (2021)

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
par: Gawrychowski, Pawel, et autres
Publié: (2024)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
par: Casel, Katrin, et autres
Publié: (2019)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
par: Huiberts, Sophie, et autres
Publié: (2022)

Efficiently Finding All Minimal and Shortest Absent Subsequences in a String
par: Manea, Florin, et autres
Publié: (2025)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
par: Adamson, Duncan, et autres
Publié: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
par: Heineman, George T., et autres
Publié: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
par: Hwang, Samuel, et autres
Publié: (2024)

Subsequence Matching and LCS with Segment Number Constraints
par: Yonemoto, Yuki, et autres
Publié: (2024)

Lower Bounds for Matroid Optimization Problems with a Linear Constraint
par: Doron-Arad, Ilan, et autres
Publié: (2023)

Improved Upper Bounds for the Directed Flow-Cut Gap
par: Bodwin, Greg, et autres
Publié: (2026)

A Subquadratic Bound for Online Bisection
par: Bienkowski, Marcin, et autres
Publié: (2023)

FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
par: Lanzinger, Matthias, et autres
Publié: (2023)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
par: Croquevielle, Luis Alberto, et autres
Publié: (2026)

Subsequence Covers of Words
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

The Complexity of Maximal Common Subsequence Enumeration
par: Buzzega, Giovanni, et autres
Publié: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
par: Yoshida, Yuichi
Publié: (2026)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
par: Boneh, Itai, et autres
Publié: (2025)

New Algorithms and Lower Bounds for Streaming Tournaments
par: Ghosh, Prantar, et autres
Publié: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
par: Chen, Yu, et autres
Publié: (2024)

Double Exponential Lower Bound for Telephone Broadcast
par: Tale, Prafullkumar
Publié: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
par: Jayaram, Rajesh, et autres
Publié: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
par: Doron-Arad, Ilan, et autres
Publié: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
par: Chen, Yu, et autres
Publié: (2026)

Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
par: Räcke, Harald, et autres
Publié: (2024)

A Lower Bound for Light Spanners in General Graphs
par: Bodwin, Greg, et autres
Publié: (2024)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
par: Funke, Daniel, et autres
Publié: (2024)

Improved Lower Bounds for Privacy under Continual Release
par: Aryanfard, Bardiya, et autres
Publié: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
par: Fleming, Noah, et autres
Publié: (2026)

Lower Bounds for Non-adaptive Local Computation Algorithms
par: Azarmehr, Amir, et autres
Publié: (2025)

Lower Bounds on Tree Covers
par: Chen, Yu, et autres
Publié: (2025)

Two New Upper Bounds for the Maximum k-plex Problem
par: Zheng, Jiongzhi, et autres
Publié: (2023)

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
par: Caporrella, Matteo, et autres
Publié: (2026)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
par: Bodwin, Greg, et autres
Publié: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
par: Chitnis, Rajesh, et autres
Publié: (2024)

A Tight Lower Bound for Cycle Detection in Grid Graphs
par: Au, Andrew
Publié: (2026)

Tight Lower Bounds for Central String Queries in Compressed Space
par: Kempa, Dominik, et autres
Publié: (2025)

Tight Static Lower Bounds for Non-Adaptive Data Structures
par: Persiano, Giuseppe, et autres
Publié: (2020)