Papers for stringologist (2018)
Contents
- How Much Different Are Two Words with Different Shortest Periods.
- Adaptive Cuckoo Filters.
- Hybrid Indexing Revisited.
- Simple, Fast and Lightweight Parallel Wavelet Tree Construction.
- A Linear-Space Data Structure for Range-LCP Queries in Poly-Logarithmic Time.
- Computing longest common square subsequences.
- Faster Online Elastic Degenerate String Matching.
- Linear-Time Algorithm for Long LCF with k Mismatches.
- Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
- Longest Lyndon Substring After Edit.
- Longest substring palindrome after edit.
- Lyndon Factorization of Grammar Compressed Texts Revisited.
- Maximal Common Subsequence Algorithms.
- On Undetected Redundancy in the Burrows-Wheeler Transform.
- Online LZ77 Parsing and Matching Statistics with RLBWTs.
- Order-Preserving Pattern Matching Indeterminate Strings.
- Slowing Down Top Trees for Better Worst-Case Compression.
- A Dynamic Compressed Self-Index for Highly Repetitive Text Collections.
- A Grammar Compression Algorithm Based on Induced Suffix Sorting.
- A Hybrid Approach for Wind Tunnel Data Compression.
- Compact Encoding for Galled-Trees and Its Applications.
- Compact Representations of Event Sequences.
- Compaction of Church Numerals for Higher-Order Compression.
- Compressed Hierarchical Clustering.
- Constant Delay Traversal of Compressed Graphs.
- Delta-Huffman Coding of Unbounded Integers.
- Efficient Processing of top-K Vector-Raster Queries Over Compressed Data.
- Engineering Compressed Static Functions.
- Exploiting Computation-Friendly Graph Compression Methods for Adjacency-Matrix Multiplication.
- Fast and Efficient Compression of Next Generation Sequencing Data.
- Fibonacci Based Compressed Suffix Array.
- K-Means Algorithm Over Compressed Binary Data.
- LZ77 Like Lossy Transformation of Quality Scores.
- Lapped Transforms Based Image Recovery for Block Compressed Sensing.
- Optimal In-Place Suffix Sorting.
- Practical Succinct Text Indexes in External Memory.
- Run Compressed Rank/Select for Large Alphabets.
- The Bits Between Proteins.
- Two-Dimensional Block Trees.
- Block Sorting-Based Transformations on Words: Beyond the Magic BWT.
- The Runs Theorem and Beyond.
- Dynamic Trees with Almost-Optimal Access Cost.
- Edit Distance with Block Operations.
- Improved Time and Space Bounds for Dynamic Range Mode.
- Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs.
- On the Decision Tree Complexity of String Matching.
- On the Worst-Case Complexity of TimSort.
- String Attractors: Verification and Optimization.
- Two-Dimensional Maximal Repetitions.
- Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.
- Bloom Filters, Adaptivity, and the Dictionary Problem.
- PanORAMa: Oblivious RAM with Logarithmic Overhead.
- Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS.
- Edit Distance between Unrooted Trees in Cubic Time.
- Scalable Construction of Text Indexes with Thrill.
- Encoding Two-Dimensional Range Top-k Queries Revisited.
- Longest Unbordered Factor in Quasilinear Time.
- Multi-Finger Binary Search Trees.
- Succinct Data Structures for Chordal Graphs.
- Tree Path Majority Data Structures.
- Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds.
- An Efficient Representation of Partitions of Integers.
- LZ-ABT: A Practical Algorithm for α-Balanced Grammar Compression.
- On the Expected Number of Distinct Gapped Palindromic Factors.
- Node Similarity with q -Grams for Real-World Labeled Networks.
- Bubble-Flip - A New Generation Algorithm for Prefix Normal Words.
- On Periodicity Lemma for Partial Words.
- Compressed Indexing with Signature Grammars.
- On the Approximation Ratio of Lempel-Ziv Parsing.
- Property Suffix Array with Applications.
- Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays.
- Fast Entropy-Bounded String Dictionary Look-Up with Mismatches.
- Dictionary Matching in Elastic-Degenerate Texts with Applications in Searching VCF Files On-line.
- Fast matching statistics in small space.
- Privacy-Preserving String Edit Distance with Moves.
- Improved bounds for testing Dyck languages.
- In-Place Sparse Suffix Sorting.
- Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
- Lempel-Ziv: a “one-bit catastrophe” but not a tragedy.
- Multivariate Fine-Grained Complexity of Longest Common Subsequence.
- Optimal Dynamic Strings.
- Optimal-Time Text Indexing in BWT-runs Bounded Space.
- The Entropy of Backwards Analysis.
- Time and Space Efficient Representations of Distributive Lattices.
- Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
- Duel and Sweep Algorithm for Order-Preserving Pattern Matching.
- Longest Common Prefixes with k-Mismatches and Applications.
- New Variants of Pattern Matching with Constants and Variables.
- A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance.
- Block Palindromes: A New Generalization of Palindromes.
- Compressed Communication Complexity of Longest Common Prefixes.
- Computing Burrows-Wheeler Similarity Distributions for String Collections.
- Efficient Computation of Sequence Mappability.
- Faster Recovery of Approximate Periods over Edit Distance.
- Longest Common Prefixes with k-Errors and Applications.
- Longest Property-Preserved Common Factor.
- Maximal Motif Discovery in a Sliding Window.
- On Extended Special Factors of a Word.
- Recovering, Counting and Enumerating Strings from Forward and Backward Suffix Arrays.
- Searching for a Modified Pattern in a Changing Text.
- An Improved Bound for Random Binary Search Trees with Concurrent Insertions.
- Computing the Longest Common Prefix of a Context-free Language in Polynomial Time.
- Improving the Upper Bound on the Length of the Shortest Reset Word.
- Relations Between Greedy and Bit-Optimal LZ77 Encodings.
- Space-Efficient Algorithms for Longest Increasing Subsequence.
- String Periods in the Order-Preserving Model.
- Succinct Oblivious RAM.
- Sums of Palindromes: an Approach via Automata.
- Upper and Lower Bounds for Dynamic Data Structures on Strings.
- At the roots of dictionary compression: string attractors.
- Explicit binary tree codes with polylogarithmic size alphabet.
- Smooth heaps and a dual view of self-adjusting data structures.
- Synchronization strings: explicit constructions, local decoding, and applications.
- Succinct Dynamic One-Dimensional Point Reporting.
- A Multi-labeled Tree Edit Distance for Comparing “Clonal Trees” of Tumor Progression.
- A Succinct Solution to Rmap Alignment.
- Degenerate String Comparison and Applications.
- Detecting Mutations by eBWT.
- External memory BWT and LCP computation for sequence collections with applications.
- Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time.
- PRINCE: Accurate Approximation of the Copy Number of Tandem Repeats.
- Prefix-Free Parsing for Building Big BWTs.
- On Multiple Longest Common Subsequence and Common Motifs with Gaps (Extended Abstract).
Algorithmica 2018
- Crochemore’s Partitioning on Weighted Strings and Applications.
- Dynamic Path Queries in Linear Space.
- Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation.
- Guest Editorial: Special Issue on Compact Data Structures.
- LZ77 Computation Based on the Run-Length Encoded BWT.
- Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees.
- Lempel-Ziv-78 Compressed String Dictionaries.
Algorithms 2018
- DenseZDD: A Compact and Fast Index for Families of Sets.
- Sliding Suffix Tree.
- STAble: a novel approach to de novo assembly of RNA-seq data and its application in a metabolic model network based metatranscriptomic workflow.
- CNEFinder: finding conserved non-coding elements in genomes.
- Practical dynamic de Bruijn graphs.
Comput. J. 2018
- Relative Suffix Trees.
Dagstuhl Reports 2018
- Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281).
- On Abelian Longest Common Factor with and without RLE.
IEICE Trans. Inf. Syst. 2018
- Approximate Frequent Pattern Discovery in Compressed Space.
Inf. Comput. 2018
- Alignment-free sequence comparison using absent words.
Inf. Process. Lett. 2018
- A hardness result and new algorithm for the longest common palindromic subsequence problem.
- Algorithms for anti-powers in strings.
Int. J. Found. Comput. Sci. 2018
- Bidirectional Variable-Order de Bruijn Graphs.
- Diverse Palindromic Factorization is NP-Complete.
- Dynamic RLE-Compressed Edit Distance Tables Under General Weighted Cost Functions.
- Fast Average-Case Pattern Matching on Weighted Sequences.
- Palindromic Decompositions with Gaps and Errors.
- m-Bonsai: A Practical Compact Dynamic Trie.
J. Discrete Algorithms 2018
- A faster implementation of online RLBWT and its application to LZ77 parsing.
- A separation between RLSLPs and LZ77.
- Algorithms and combinatorial properties on shortest unique palindromic substrings.
- Lyndon array construction during Burrows-Wheeler inversion.
Theor. Comput. Sci. 2018
- Advances in Algorithms & Combinatorics on Strings (Honoring 60th birthday for Prof. Costas S. Iliopoulos).
- Efficient algorithms for shortest partial seeds in words.
- Period recovery of strings over the Hamming and edit distances.
- The nearest colored node in a tree.
- Time-space trade-offs for Lempel-Ziv compressed indexing.
Theory Comput. Syst. 2018
- Finger Search in Grammar-Compressed Strings.
- 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.