Pawel Gawrychowski

Tomohiro I

Shunsuke Inenaga

Dominik Köppl

Theory Comput. Syst., 2018

The complexity of mean payoff games using universal graphs.

[BibT_eX]

[DOI]

Nathanaël Fijalkow

Pierre Ohlmann

CoRR, 2018

Slowing Down Top Trees for Better Worst-Case Bounds.

[BibT_eX]

[DOI]

CoRR, 2018

Better Tradeoffs for Exact Distance Oracles in Planar Graphs.

[BibT_eX]

[DOI]

Shay Mozes

Christian Wulff-Nilsen

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ(n5/3) Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.

[BibT_eX]

[DOI]

Fabian Kuhn

Jakub Lopuszanski

Konstantinos Panagiotou

Pascal Su

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Optimal Dynamic Strings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Compression for the Planar Graph Metric.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Fast Entropy-Bounded String Dictionary Look-Up with Mismatches.

[BibT_eX]

[DOI]

Gad M. Landau

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Faster FPTAS for #Knapsack.

[BibT_eX]

[DOI]

Liran Markin

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Faster Construction of Greedy Consensus Trees.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Improved Bounds for Shortest Paths in Dense Distance Graphs.

[BibT_eX]

[DOI]

Adam Karczmarz

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Edit Distance between Unrooted Trees in Cubic Time.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Edit Distance with Block Operations.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Near-Optimal Distance Emulator for Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Slowing Down Top Trees for Better Worst-Case Compression.

[BibT_eX]

[DOI]

Proceedings of the Annual Symposium on Combinatorial Pattern Matching, 2018

Average-Case Behavior of k-Shortest Path Algorithms.

[BibT_eX]

[DOI]

Alexander Schickedanz

Deepak Ajwani

Ulrich Meyer

Proceedings of the Complex Networks and Their Applications VII, 2018

2017

Longest Gapped Repeats and Palindromes.

[BibT_eX]

[DOI]

Marius Dumitran

Discret. Math. Theor. Comput. Sci., 2017

Optimal trade-offs for pattern matching with k mismatches.

[BibT_eX]

[DOI]

CoRR, 2017

Existential length universality.

[BibT_eX]

[DOI]

CoRR, 2017

A Faster Construction of Phylogenetic Consensus Trees.

[BibT_eX]

[DOI]

CoRR, 2017

Better Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.

[BibT_eX]

[DOI]

Jakub Lopuszanski

CoRR, 2017

Optimal Query Time for Encoding Range Majority.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Distinct Squares in Circular Words.

[BibT_eX]

[DOI]

Mika Amit

Proceedings of the String Processing and Information Retrieval, 2017

Sparse Suffix Tree Construction in Optimal Time and Space.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Optimal Distance Labeling Schemes for Trees.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Dispersion on Trees.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem.

[BibT_eX]

[DOI]

Piotr Ostropolski-Nalewaja

Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching, 2017

2016

Order-preserving pattern matching with k mismatches.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Longest common extensions in trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Computing minimal and maximal suffixes of a substring.

[BibT_eX]

[DOI]

Ignat I. Kolesnichenko

Theor. Comput. Sci., 2016

A note on distance labeling in planar graphs.

[BibT_eX]

[DOI]

CoRR, 2016

Sublinear-Space Distance Labeling Using Hubs.

[BibT_eX]

[DOI]

Adrian Kosowski

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Randomized Algorithms for Finding a Majority Element.

[BibT_eX]

[DOI]

Jukka Suomela

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

Efficiently Finding All Maximal alpha-gapped Repeats.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Bookmarks in Grammar-Compressed Strings.

[BibT_eX]

[DOI]

Patrick Hagge Cording

Proceedings of the String Processing and Information Retrieval, 2016

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs.

[BibT_eX]

[DOI]

Adrian Kosowski

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

LZ77 Factorisation of Trees.

[BibT_eX]

[DOI]

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Faster Longest Common Extension Queries in Strings over General Alphabets.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching, 2016

2015

Approximate pattern matching in LZ77-compressed texts.

[BibT_eX]

[DOI]

Simon J. Puglisi

J. Discrete Algorithms, 2015

Even Simpler Distance Labeling for (Sparse) Graphs.

[BibT_eX]

[DOI]

Adrian Kosowski

CoRR, 2015

Efficiently Finding All Maximal $α$-gapped Repeats.

[BibT_eX]

[DOI]

CoRR, 2015

Testing k-binomial equivalence.

[BibT_eX]

[DOI]

Dominik D. Freydenberger

CoRR, 2015

Limit Behavior of the Multi-agent Rotor-Router System.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Computing the Longest Unbordered Substring.

[BibT_eX]

[DOI]

Gregory Kucherov

Benjamin Sach

Proceedings of the String Processing and Information Retrieval, 2015

Wavelet Trees Meet Suffix Trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Strong Inapproximability of the Shortest Reset Word.

[BibT_eX]

[DOI]

Damian Straszak

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Optimal Encodings for Range Top- k k , Selection, and Min-Max.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search.

[BibT_eX]

[DOI]

Shay Mozes

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Longest α-Gapped Repeat and Palindrome.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

Approximating LZ77 via Small-Space Multiple-Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

Queries on LZ-Bounded Encodings.

[BibT_eX]

[DOI]

Alberto Ordóñez Pereira

Simon J. Puglisi

Yasuo Tabei

Proceedings of the 2015 Data Compression Conference, 2015

Encodings of Range Maximum-Sum Segment Queries and Applications.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

Alphabet-Dependent String Searching with Wexponential Search Trees.

[BibT_eX]

[DOI]

Johannes Fischer

Proceedings of the Combinatorial Pattern Matching - 26th Annual Symposium, 2015

2014

Validating the Knuth-Morris-Pratt Failure Function, Fast and Online.

[BibT_eX]

[DOI]

Lukasz Jez

Theory Comput. Syst., 2014

Simple and efficient LZW-compressed multiple pattern matching.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2014

Tight tradeoffs for approximating palindromes in streams.

[BibT_eX]

[DOI]

CoRR, 2014

Optimal Encodings for Range Min-Max and Top-k.

[BibT_eX]

[DOI]

CoRR, 2014

Lock-in Problem for Parallel Rotor-router Walks.

[BibT_eX]

[DOI]

CoRR, 2014

Testing Generalised Freeness of Words.

[BibT_eX]

[DOI]

Dirk Nowotka

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

LZ77-Based Self-indexing with Faster Pattern Matching.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Euclidean TSP with Few Inner Points in Linear Space.

[BibT_eX]

[DOI]

Damian Rusak

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

Improved Submatrix Maximum Queries in Monge Matrices.

[BibT_eX]

[DOI]

Shay Mozes

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Weighted Ancestors in Suffix Trees.

[BibT_eX]

[DOI]

Moshe Lewenstein

Proceedings of the Algorithms - ESA 2014, 2014

Computing Minimal and Maximal Suffixes of a Substring Revisited.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching - 25th Annual Symposium, 2014

2013

Optimal Pattern Matching in LZW Compressed Strings.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

Minimax trees in linear time with applications.

[BibT_eX]

[DOI]

Eur. J. Comb., 2013

Beating O(nm) in approximate LZW-compressed pattern matching.

[BibT_eX]

[DOI]

Damian Straszak

CoRR, 2013

Substring Suffix Selection.

[BibT_eX]

[DOI]

CoRR, 2013

Finding Pseudo-repetitions.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Minimal Discriminating Words Problem Revisited.

[BibT_eX]

[DOI]

Gregory Kucherov

Yakov Nekrich

Proceedings of the String Processing and Information Retrieval, 2013

Beating $\mathcal{O}(nm)$ in Approximate LZW-Compressed Pattern Matching.

[BibT_eX]

[DOI]

Damian Straszak

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Alphabetic Minimax Trees in Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2013

Converting SLP to LZ78 in almost Linear Time.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

Discovering Hidden Repetitions in Words.

[BibT_eX]

[DOI]

Dirk Nowotka

Proceedings of the Nature of Computation. Logic, Algorithms, Applications, 2013

Heaviest Induced Ancestors and Longest Common Substrings.

[BibT_eX]

[DOI]

Yakov Nekrich

Proceedings of the 25th Canadian Conference on Computational Geometry, 2013

2012

(Really) Tight bounds for dispatching binary methods

[BibT_eX]

[DOI]

CoRR, 2012

Linear-Space Substring Range Counting over Polylogarithmic Alphabets

[BibT_eX]

[DOI]

CoRR, 2012

Tying up the loose ends in fully LZW-compressed pattern matching.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Faster Algorithm for Computing the Edit Distance between SLP-Compressed Strings.

[BibT_eX]

[DOI]

Proceedings of the String Processing and Information Retrieval, 2012

A Faster Grammar-Based Self-index.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2012

2011

A Faster LZ77-Based Index

[BibT_eX]

[DOI]

CoRR, 2011

Chrobak Normal Form Revisited, with Applications.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2011

On Minimising Automata with Errors.

[BibT_eX]

[DOI]

Andreas Maletti

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Faster Approximate Pattern Matching in Compressed Repetitive Texts.

[BibT_eX]

[DOI]

Simon J. Puglisi

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

On the problem of freeness of multiplicative matrix semigroups.

[BibT_eX]

[DOI]

Marin Gutan

Andrzej Kisielewicz

Theor. Comput. Sci., 2010

Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2010

Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2010

Grammar-Based Compression in a Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2010

2009

Optimal, online validation of the pi and pi' failure functions

[BibT_eX]

[DOI]

Lukasz Jez

CoRR, 2009

Hyper-minimisation Made Efficient.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

2008

Minimax Trees in Linear Time

[BibT_eX]

[DOI]

CoRR, 2008

2-Synchronizing Words.

[BibT_eX]

[DOI]