Image de couverture de livre

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Casel, Katrin, Day, Joel D., Fleischmann, Pamela, Kociumaka, Tomasz, Manea, Florin, Schmid, Markus L.
Format:	Preprint
Publié:	2019
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

On Approximating Cutwidth and Pathwidth
par: Bansal, Nikhil, et autres
Publié: (2023)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
par: Duyster, Anouk, et autres
Publié: (2026)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
par: Manea, Florin, et autres
Publié: (2024)

Time-Optimal Construction of String Synchronizing Sets
par: Ellert, Jonas, et autres
Publié: (2026)

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

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
par: Kempa, Dominik, et autres
Publié: (2025)

Fine-Grained Complexity of Regular Path Queries
par: Casel, Katrin, et autres
Publié: (2021)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
par: Kociumaka, Tomasz, et autres
Publié: (2014)

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

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

Emit As You Go: Enumerating Edges of a Spanning Tree
par: Casel, Katrin, et autres
Publié: (2025)

$k$-Universality of Regular Languages Revisited
par: Adamson, Duncan, et autres
Publié: (2025)

Cutwidth and Crossings
par: Rauch, Johannes, et autres
Publié: (2025)

Near-Optimal Property Testers for Pattern Matching
par: Jin, Ce, et autres
Publié: (2025)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
par: Duyster, Anouk, et autres
Publié: (2025)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
par: Gorbachev, Egor, et autres
Publié: (2024)

Space-Efficient k-Mismatch Text Indexes
par: Kociumaka, Tomasz, et autres
Publié: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
par: Kempa, Dominik, et autres
Publié: (2025)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
par: Kempa, Dominik, et autres
Publié: (2024)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
par: Kociumaka, Tomasz, et autres
Publié: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
par: Kempa, Dominik, et autres
Publié: (2023)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
par: Das, Debarati, et autres
Publié: (2025)

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

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
par: Tale, Prafullkumar
Publié: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
par: Gawrychowski, Paweł, et autres
Publié: (2024)

Pattern Matching under Weighted Edit Distance
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

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

The Communication Complexity of Pattern Matching with Edits Revisited
par: Kociumaka, Tomasz, et autres
Publié: (2026)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
par: Bathie, Gabriel, et autres
Publié: (2023)

On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
par: Aminian, Aida, et autres
Publié: (2025)

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

Combining Crown Structures for Vulnerability Measures
par: Casel, Katrin, et autres
Publié: (2024)

Cutwidth Bounds via Vertex Partitions
par: Amarilli, Antoine, et autres
Publié: (2025)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
par: Goldenberg, Elazar, et autres
Publié: (2022)

Faster Algorithms for Longest Common Substring
par: Charalampopoulos, Panagiotis, et autres
Publié: (2021)

The Primal Pathwidth SETH
par: Lampis, Michael
Publié: (2024)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

On the Communication Complexity of Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

Approximate Circular Pattern Matching
par: Charalampopoulos, Panagiotis, et autres
Publié: (2022)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
par: Greilhuber, Jakob, et autres
Publié: (2026)