StringologyTimes

Papers for stringologist (2018)

Contents

AIAI (Workshops) 2018

  1. How Much Different Are Two Words with Different Shortest Periods.

ALENEX 2018

  1. Adaptive Cuckoo Filters.
  2. Hybrid Indexing Revisited.
  3. Simple, Fast and Lightweight Parallel Wavelet Tree Construction.

COCOON 2018

  1. A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time.

CPM 2018

  1. A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications.
  2. A Succinct Four Russians Speedup for Edit Distance Computation and One-against-many Banded Alignment.
  3. Can a permutation be sorted by best short swaps?.
  4. Computing longest common square subsequences.
  5. Dualities in Tree Representations.
  6. Fast Matching-based Approximations for Maximum Duo-Preservation String Mapping and its Weighted Variant.
  7. Faster Online Elastic Degenerate String Matching.
  8. Front Matter, Table of Contents, Preface, Conference Organization.
  9. Linear-Time Algorithm for Long LCF with k Mismatches.
  10. Linear-time algorithms for the subpath kernel.
  11. Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
  12. Longest Lyndon Substring After Edit.
  13. Longest substring palindrome after edit.
  14. Lyndon Factorization of Grammar Compressed Texts Revisited.
  15. Maximal Common Subsequence Algorithms.
  16. Nearest constrained circular words.
  17. Non-Overlapping Indexing - Cache Obliviously.
  18. On Undetected Redundancy in the Burrows-Wheeler Transform.
  19. On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure.
  20. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  21. Order-Preserving Pattern Matching Indeterminate Strings.
  22. Quasi-Periodicity Under Mismatch Errors.
  23. Slowing Down Top Trees for Better Worst-Case Compression.
  24. Superstrings with multiplicities.
  25. The Heaviest Induced Ancestors Problem Revisited.

DCC 2018

  1. A Dynamic Compressed Self-Index for Highly Repetitive Text Collections.
  2. A Grammar Compression Algorithm Based on Induced Suffix Sorting.
  3. A Hybrid Approach for Wind Tunnel Data Compression.
  4. Compact Encoding for Galled-Trees and Its Applications.
  5. Compact Representations of Event Sequences.
  6. Compaction of Church Numerals for Higher-Order Compression.
  7. Compressed Hierarchical Clustering.
  8. Constant Delay Traversal of Compressed Graphs.
  9. Delta-Huffman Coding of Unbounded Integers.
  10. Efficient Processing of top-K Vector-Raster Queries Over Compressed Data.
  11. Engineering Compressed Static Functions.
  12. Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication.
  13. Fast and Efficient Compression of Next Generation Sequencing Data.
  14. Fibonacci Based Compressed Suffix Array.
  15. K-Means Algorithm Over Compressed Binary Data.
  16. LZ77 Like Lossy Transformation of Quality Scores.
  17. Lapped Transforms Based Image Recovery for Block Compressed Sensing.
  18. Optimal In-Place Suffix Sorting.
  19. Practical Succinct Text Indexes in External Memory.
  20. Run Compressed Rank/Select for Large Alphabets.
  21. The Bits Between Proteins.
  22. Two-Dimensional Block Trees.

DLT 2018

  1. Block Sorting-Based Transformations on Words: Beyond the Magic BWT.
  2. The Runs Theorem and Beyond.

ESA 2018

  1. Dynamic Trees with Almost-Optimal Access Cost.
  2. Edit Distance with Block Operations.
  3. Improved Time and Space Bounds for Dynamic Range Mode.
  4. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs.
  5. On the Decision Tree Complexity of String Matching.
  6. On the Worst-Case Complexity of TimSort.
  7. String Attractors: Verification and Optimization.
  8. Two-Dimensional Maximal Repetitions.

FOCS 2018

  1. Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.
  2. Bloom Filters, Adaptivity, and the Dictionary Problem.
  3. PanORAMa: Oblivious RAM with Logarithmic Overhead.

FSTTCS 2018

  1. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.

ICALP 2018

  1. Edit Distance between Unrooted Trees in Cubic Time.

IEEE BigData 2018

  1. Scalable Construction of Text Indexes with Thrill.

ISAAC 2018

  1. Encoding Two-Dimensional Range Top-k Queries Revisited.
  2. Longest Unbordered Factor in Quasilinear Time.
  3. Multi-Finger Binary Search Trees.
  4. Succinct Data Structures for Chordal Graphs.
  5. Tree Path Majority Data Structures.

ITCS 2018

  1. Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.

IWOCA 2018

  1. An Efficient Representation of Partitions of Integers.
  2. LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression.
  3. On the Expected Number of Distinct Gapped Palindromic Factors.

KDD 2018

  1. Node Similarity with q -Grams for Real-World Labeled Networks.

LATA 2018

  1. Bubble-Flip - A New Generation Algorithm for Prefix Normal Words.
  2. On Periodicity Lemma for Partial Words.

LATIN 2018

  1. Compressed Indexing with Signature Grammars.
  2. On the Approximation Ratio of Lempel-Ziv Parsing.
  3. Property Suffix Array with Applications.

MFCS 2018

  1. Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
  2. Fast Entropy-Bounded String Dictionary Look-Up with Mismatches.

SEA 2018

  1. Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching VCF Files On-line.
  2. Fast matching statistics in small space.

SISAP 2018

  1. Privacy-Preserving String Edit Distance with Moves.

SODA 2018

  1. Improved bounds for testing Dyck languages.
  2. In-Place Sparse Suffix Sorting.
  3. Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
  4. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy.
  5. Multivariate Fine-Grained Complexity of Longest Common Subsequence.
  6. Optimal Dynamic Strings.
  7. Optimal-Time Text Indexing in BWT-runs Bounded Space.
  8. The Entropy of Backwards Analysis.
  9. Time and Space Efficient Representations of Distributive Lattices.
  10. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).

SOFSEM 2018

  1. Duel and Sweep Algorithm for Order-Preserving Pattern Matching.
  2. Longest Common Prefixes with k-Mismatches and Applications.
  3. New Variants of Pattern Matching with Constants and Variables.

SOSA 2018

  1. A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance.

SPIRE 2018

  1. 3DGraCT: A Grammar-Based Compressed Representation of 3D Trajectories.
  2. Adaptive Computation of the Discrete Fréchet Distance.
  3. Better Heuristic Algorithms for the Repetition Free LCS and Other Variants.
  4. Block Palindromes: A New Generalization of Palindromes.
  5. Compressed Communication Complexity of Longest Common Prefixes.
  6. Compressed Range Minimum Queries.
  7. Computing Burrows-Wheeler Similarity Distributions for String Collections.
  8. Early Commenting Features for Emotional Reactions Prediction.
  9. Efficient Computation of Sequence Mappability.
  10. Fast Wavelet Tree Construction in Practice.
  11. Fast and Effective Neural Networks for Translating Natural Language into Denotations.
  12. Faster Recovery of Approximate Periods over Edit Distance.
  13. Faster and Smaller Two-Level Index for Network-Based Trajectories.
  14. Indexed Dynamic Programming to Boost Edit Distance and LCSS Computation.
  15. Linear-Time Online Algorithm Inferring the Shortest Path from a Walk.
  16. Longest Common Prefixes with k-Errors and Applications.
  17. Longest Property-Preserved Common Factor.
  18. Maximal Motif Discovery in a Sliding Window.
  19. New Structures to Solve Aggregated Queries for Trips over Public Transportation Networks.
  20. On Extended Special Factors of a Word.
  21. Optimal In-Place Suffix Sorting.
  22. Recoloring the Colored de Bruijn Graph.
  23. Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.
  24. Searching for a Modified Pattern in a Changing Text.
  25. The Colored Longest Common Prefix Array Computed via Sequential Scans.
  26. Towards a Compact Representation of Temporal Rasters.
  27. Trickier XBWT Tricks.
  28. Truncated DAWGs and Their Application to Minimal Absent Word Problem.

STACS 2018

  1. An Improved Bound for Random Binary Search Trees with Concurrent Insertions.
  2. Computing the Longest Common Prefix of a Context-free Language in Polynomial Time.
  3. Improving the Upper Bound on the Length of the Shortest Reset Word.
  4. Relations Between Greedy and Bit-Optimal LZ77 Encodings.
  5. Space-Efficient Algorithms for Longest Increasing Subsequence.
  6. String Periods in the Order-Preserving Model.
  7. Succinct Oblivious RAM.
  8. Sums of Palindromes: an Approach via Automata.
  9. Upper and Lower Bounds for Dynamic Data Structures on Strings.

STOC 2018

  1. At the roots of dictionary compression: string attractors.
  2. Explicit binary tree codes with polylogarithmic size alphabet.
  3. Smooth heaps and a dual view of self-adjusting data structures.
  4. Synchronization strings: explicit constructions, local decoding, and applications.

SWAT 2018

  1. Succinct Dynamic One-Dimensional Point Reporting.

Stringology 2018

  1. A Faster V-order String Comparison Algorithm.
  2. Constrained Approximate Subtree Matching by Finite Automata.
  3. Discovery of Regulatory Motifs in DNA.
  4. Fast and Simple Algorithms for Computing both LCSk and LCSk+.
  5. Fibonacci Based Compressed Suffix Array.
  6. O(n log n)-time Text Compression by LZ-style Longest First Substitution.
  7. On Baier’s Sort of Maximal Lyndon Substrings.
  8. Parameterized Dictionary Matching with One Gap.
  9. Right-to-left Online Construction of Parameterized Position Heaps.
  10. Synchronizing Dynamic Huffman Codes.
  11. Three Strategies for the Dead-Zone String Matching Algorithm.

TFPIE@TFP 2018

  1. Vector Programming Using Generative Recursion.

WABI 2018

  1. A Multi-labeled Tree Edit Distance for Comparing “Clonal Trees” of Tumor Progression.
  2. A Succinct Solution to Rmap Alignment.
  3. Degenerate String Comparison and Applications.
  4. Detecting Mutations by eBWT.
  5. External memory BWT and LCP computation for sequence collections with applications.
  6. Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time.
  7. PRINCE: Accurate Approximation of the Copy Number of Tandem Repeats.
  8. Prefix-Free Parsing for Building Big BWTs.

WALCOM 2018

  1. On Multiple Longest Common Subsequence and Common Motifs with Gaps (Extended Abstract).

Algorithmica 2018

  1. Crochemore’s Partitioning on Weighted Strings and Applications.
  2. Dynamic Path Queries in Linear Space.
  3. Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.
  4. Guest Editorial: Special Issue on Compact Data Structures.
  5. LZ77 Computation Based on the Run-Length Encoded BWT.
  6. Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees.
  7. Lempel-Ziv-78 Compressed String Dictionaries.

Algorithms 2018

  1. DenseZDD: A Compact and Fast Index for Families of Sets.
  2. Sliding Suffix Tree.

BMC Bioinform. 2018

  1. STAble: a novel approach to de novo assembly of RNA-seq data and its application in a metabolic model network based metatranscriptomic workflow.

Bioinform. 2018

  1. CNEFinder: finding conserved non-coding elements in genomes.
  2. Practical dynamic de Bruijn graphs.

CoRR 2018

  1. A Compact Representation for Trips over Networks built on self-indexes.
  2. A Fast Combination of AES Encryption and LZ4 Compression Algorithms.
  3. A Faster External Memory Priority Queue with DecreaseKeys.
  4. A Grammar-based Compressed Representation of 3D Trajectories.
  5. A Simple Algorithm for Computing the Document Array.
  6. A Simple and Space Efficient Segment Tree Implementation.
  7. A Weighted Generalization of the Graham-Diaconis Inequality for Ranked List Similarity.
  8. ALLSAT compressed with wildcards: Partitionings and face-numbers of simplicial complexes.
  9. Adaptive Shivers Sort: An Alternative Sorting Algorithm.
  10. Algorithms for Anti-Powers in Strings.
  11. Alignment-free sequence comparison using absent words.
  12. An O(N) Sorting Algorithm: Machine Learning Sorting.
  13. An optimized Parallel Failure-less Aho-Corasick algorithm for DNA sequence matching.
  14. Another Proof of Cuckoo hashing with New Variants.
  15. Approximate Nearest Neighbors in Limited Space.
  16. Approximate Online Pattern Matching in Sub-linear Time.
  17. Approximate Query Processing over Static Sets and Sliding Windows.
  18. Approximating Approximate Pattern Matching.
  19. Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time.
  20. Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce.
  21. Assembling Omnitigs using Hidden-Order de Bruijn Graphs.
  22. BDDs Naturally Represent Boolean Functions, and ZDDs Naturally Represent Sets of Sets.
  23. Beating Fredman-Komlós for perfect k-hashing.
  24. Block Palindromes: A New Generalization of Palindromes.
  25. Calculation of extended gcd by normalization.
  26. Cardinality Estimators do not Preserve Privacy.
  27. Collapsing Superstring Conjecture.
  28. Compact Representations of Event Sequences.
  29. Compound Binary Search Tree and Algorithms.
  30. Compressed Communication Complexity of Longest Common Prefixes.
  31. Compressed Multiple Pattern Matching.
  32. Computing the k-binomial complexity of the Thue-Morse word.
  33. CuCoTrack: Cuckoo Filter Based Connection Tracking.
  34. DeepZip: Lossless Data Compression using Recurrent Neural Networks.
  35. Design and Implementation of Dynamic Memory Management in a Reversible Object-Oriented Programming Language.
  36. Detecting Mutations by eBWT.
  37. Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors.
  38. Distinct Sampling on Streaming Data with Near-Duplicates.
  39. Dualities in Tree Representations.
  40. Dynamic Trees with Almost-Optimal Access Cost.
  41. Dynamic all scores matrices for LCS score.
  42. Edit Distance between Unrooted Trees in Cubic Time.
  43. Efficient Computation of Sequence Mappability.
  44. Efficient Construction of a Complete Index for Pan-Genomics Read Alignment.
  45. Efficient Genomic Interval Queries Using Augmented Range Trees.
  46. Efficient Representation and Counting of Antipower Factors in Words.
  47. Efficient Single Writer Concurrency.
  48. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
  49. Eleven Simple Algorithms to Compute Fibonacci Numbers.
  50. Encoding two-dimensional range top-k queries revisited.
  51. Enhanced string factoring from alphabet orderings.
  52. Entropy bounds for grammar compression.
  53. Enumerating Cryptarithms Using Deterministic Finite Automata.
  54. External memory BWT and LCP computation for sequence collections with applications.
  55. Extra Space during Initialization of Succinct Data Structures and of Dynamical Initializable Arrays.
  56. Fast Breadth-First Search in Still Less Space.
  57. Fast Lempel-Ziv Decompression in Linear Space.
  58. Fast Locality Sensitive Hashing for Beam Search on GPU.
  59. Fast Prefix Search in Little Space, with Applications.
  60. Fast and Longest Rollercoasters.
  61. Fast entropy-bounded string dictionary look-up with mismatches.
  62. Faster Approximate(d) Text-to-Pattern L1 Distance.
  63. Faster Attractor-Based Indexes.
  64. Faster Recovery of Approximate Periods over Edit Distance.
  65. Fault Tolerant and Fully Dynamic DFS in Undirected Graphs: Simple Yet Efficient.
  66. Finding a Small Number of Colourful Components.
  67. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve.
  68. Flexible and Efficient Algorithms for Abelian Matching in Strings.
  69. From Regular Expression Matching to Parsing.
  70. Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space.
  71. Generalized Leapfrogging Samplesort: A Class of O(n log2n) Worst-Case Complexity and O(n log n) Average-Case Complexity Sorting Algorithms.
  72. Grammar-based Compression of Unranked Trees.
  73. Graph Pattern Matching Preserving Label-Repetition Constraints.
  74. Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm.
  75. Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model.
  76. Haplotype-aware graph indexes.
  77. Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming and Linear Algebra.
  78. Improved Time and Space Bounds for Dynamic Range Mode.
  79. Improved Upper Bounds on all Maximal α-gapped Repeats and Palindromes.
  80. Improved bounds for multipass pairing heaps and path-balanced binary search trees.
  81. Improving Similarity Search with High-dimensional Locality-sensitive Hashing.
  82. Indexed Dynamic Programming to boost Edit Distance and LCSS Computation.
  83. Know When to Fold ‘Em: Self-Assembly of Shapes by Folding in Oritatami.
  84. LZRR: LZ77 Parsing with Right Reference.
  85. Linear-Time Algorithm for Long LCF with k Mismatches.
  86. Linear-Time In-Place DFS and BFS in the Restore Model.
  87. List Decoding with Double Samplers.
  88. Local Decodability of the Burrows-Wheeler Transform.
  89. Locally Consistent Parsing for Text Indexing in Small Space.
  90. Longest Common Factor Made Fully Dynamic.
  91. Longest Common Prefixes with k-Errors and Applications.
  92. Longest Increasing Subsequence under Persistent Comparison Errors.
  93. Longest Property-Preserved Common Factor.
  94. Longest Unbordered Factor in Quasilinear Time.
  95. Lower Bounds for Oblivious Data Structures.
  96. Lower bounds for text indexing with mismatches and differences.
  97. MR-RePair: Grammar Compression based on Maximal Repeats.
  98. Massively Parallel Dynamic Programming on Trees.
  99. MinJoin: Efficient Edit Similarity Joins via Local Hash Minimums.
  100. Minimum Segmentation for Pan-genomic Founder Reconstruction in Optimal Time.
  101. Minuet: A method to solve Sudoku puzzles by hand.
  102. Multi-finger binary search trees.
  103. Multidimensional segment trees can do range queries and updates in logarithmic time.
  104. Multivariate Fine-Grained Complexity of Longest Common Subsequence.
  105. Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing.
  106. Nearly Optimal Space Efficient Algorithm for Depth First Search.
  107. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs.
  108. Non-Empty Bins with Simple Tabulation Hashing.
  109. O(n log n)-time text compression by LZ-style longest first substitution.
  110. On Abelian Longest Common Factor with and without RLE.
  111. On Computing Average Common Substring Over Run Length Encoded Sequences.
  112. On Estimating Edit Distance: Alignment, Dimension Reduction, and Embeddings.
  113. On Infinite Prefix Normal Words.
  114. On Periodicity Lemma for Partial Words.
  115. On Undetected Redundancy in the Burrows-Wheeler Transform.
  116. On improving the approximation ratio of the r-shortest common superstring problem.
  117. On the Approximation Ratio of Greedy Parsings.
  118. On the Diameter of Tree Associahedra.
  119. On the Worst-Case Complexity of TimSort.
  120. On the discrepancy of random low degree set systems.
  121. On the tails of the limiting QuickSort density.
  122. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  123. Optimal Algorithm for Profiling Dynamic Arrays with Finite Values.
  124. Optimal Ball Recycling.
  125. Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions.
  126. Optimal Hashing in External Memory.
  127. Optimal Rank and Select Queries on Dictionary-Compressed Text.
  128. Optimal Sorting with Persistent Comparison Errors.
  129. Optimal Substring-Equality Queries with Applications to Sparse Text Indexing.
  130. Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition.
  131. Optimal streaming and tracking distinct elements with high probability.
  132. Optimizing Bloom Filter: Challenges, Solutions, and Comparisons.
  133. Orthogonal Point Location and Rectangle Stabbing Queries in 3-d.
  134. Parallel Range and Segment Queries with Augmented Maps.
  135. Parallel Working-Set Search Structures.
  136. Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry.
  137. Parallelism in Randomized Incremental Algorithms.
  138. Periodicity in Data Streams with Wildcards.
  139. Pivot Sampling in QuickXSort: Precise Analysis of QuickMergesort and QuickHeapsort.
  140. Practical Access to Dynamic Programming on Tree Decompositions.
  141. Prefix-Free Parsing for Building Big BWTs.
  142. Push-Down Trees: Optimal Self-Adjusting Complete Trees.
  143. QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting.
  144. QuickXsort - A Fast Sorting Scheme in Theory and Practice.
  145. Randen - fast backtracking-resistant random generator with AES+Feistel+Reverie.
  146. RePair in Compressed Space and Time.
  147. Reconstructing Strings from Substrings: Optimal Randomized and Average-Case Algorithms.
  148. Red-Black Trees with Constant Update Time.
  149. Relative compression of trajectories.
  150. Restructuring expression dags for efficient parallelization.
  151. Revisiting the tree edit distance and its backtracing: A tutorial.
  152. Right-to-left online construction of parameterized position heaps.
  153. Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables.
  154. Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools.
  155. Sesquickselect: One and a half pivots for cache-efficient selection.
  156. Simple Concurrent Labeling Algorithms for Connected Components.
  157. Simple and Fast BlockQuicksort using Lomuto’s Partitioning Scheme.
  158. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.
  159. Sliding Suffix Tree.
  160. Small Uncolored and Colored Choice Dictionaries.
  161. Smooth heaps and a dual view of self-adjusting data structures.
  162. Some comments on the structure of the best known networks sorting 16 elements.
  163. Sorting Real Numbers in O(n√(log n)) Time and Linear Space.
  164. Space-Efficient DFS and Applications: Simpler, Leaner, Faster.
  165. Static Data Structure Lower Bounds Imply Rigidity.
  166. Strategies for Stable Merge Sorting.
  167. Streaming dictionary matching with mismatches.
  168. String Attractors: Verification and Optimization.
  169. String Periods in the Order-Preserving Model.
  170. Strong link between BWT and XBW via Aho-Corasick automaton and applications to Run-Length Encoding.
  171. Sub-O(log n) Out-of-Order Sliding-Window Aggregation.
  172. Succinct Oblivious RAM.
  173. Succinct data structure for dynamic trees with faster queries.
  174. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations.
  175. Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets.
  176. Synchronization Strings: List Decoding for Insertions and Deletions.
  177. The Read-Optimized Burrows-Wheeler Transform.
  178. The colored longest common prefix array computed via sequential scans.
  179. The effective entropy of next/previous larger/smaller value queries.
  180. The entropy of lies: playing twenty questions with a liar.
  181. Tree Path Majority Data Structures.
  182. Tunneling on Wheeler Graphs.
  183. Two Algorithms to Find Primes in Patterns.
  184. Two-Dimensional Block Trees.
  185. Universal Compressed Text Indexing.
  186. Upper and lower bounds for dynamic data structures on strings.
  187. Using Compressed Suffix-Arrays for a Compact Representation of Temporal-Graphs.
  188. Using statistical encoding to achieve tree succinctness never seen before.
  189. Vectorized Character Counting for Faster Pattern Matching.
  190. Weighted dynamic finger in binary search trees.
  191. Wormhole: A Fast Ordered Index for In-memory Data Management.
  192. Worst-Case Efficient Sorting with QuickMergesort.
  193. Xorshift1024*, Xorshift1024+, Xorshift128+ and Xoroshiro128+ Fail Statistical Tests for Linearity.
  194. Zip Trees.
  195. copMEM: Finding maximal exact matches via sampling both genomes.
  196. k-Maximum Subarrays for Small k: Divide-and-Conquer made simpler.

Comput. J. 2018

  1. Relative Suffix Trees.

Dagstuhl Reports 2018

  1. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281).

Fundam. Informaticae 2018

  1. On Abelian Longest Common Factor with and without RLE.

IEICE Trans. Inf. Syst. 2018

  1. Approximate Frequent Pattern Discovery in Compressed Space.

Inf. Comput. 2018

  1. Alignment-free sequence comparison using absent words.

Inf. Process. Lett. 2018

  1. A hardness result and new algorithm for the longest common palindromic subsequence problem.
  2. Algorithms for anti-powers in strings.

Int. J. Found. Comput. Sci. 2018

  1. Bidirectional Variable-Order de Bruijn Graphs.
  2. Diverse Palindromic Factorization is NP-Complete.
  3. Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions.
  4. Fast Average-Case Pattern Matching on Weighted Sequences.
  5. Palindromic Decompositions with Gaps and Errors.
  6. m-Bonsai: A Practical Compact Dynamic Trie.

J. Discrete Algorithms 2018

  1. A faster implementation of online RLBWT and its application to LZ77 parsing.
  2. A separation between RLSLPs and LZ77.
  3. Algorithms and combinatorial properties on shortest unique palindromic substrings.
  4. Lyndon array construction during Burrows-Wheeler inversion.

Theor. Comput. Sci. 2018

  1. Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos).
  2. Efficient algorithms for shortest partial seeds in words.
  3. Period recovery of strings over the Hamming and edit distances.
  4. The nearest colored node in a tree.
  5. Time-space trade-offs for Lempel-Ziv compressed indexing.

Theory Comput. Syst. 2018

  1. Finger Search in Grammar-Compressed Strings.
  2. Tighter Bounds and Optimal Algorithms for All Maximal α-gapped Repeats and Palindromes - Finding All Maximal α-gapped Repeats and Palindromes in Optimal Worst Case Time on Integer Alphabets.
This site is open source. Improve this page.