Roman Kolpakov

According to our database, Roman Kolpakov authored at least 37 papers between 1995 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Lower time bounds for parallel solving of the subset sum problem by a dynamic programming algorithm.

Roman Kolpakov, Mikhail Posypkin

Concurr. Comput. Pract. Exp., August, 2024

2022

Almost optimal searching of maximal subrepetitions in a word.

Roman Kolpakov

CoRR, 2022

2021

Optimality and Complexity Analysis of a Branch-and-Bound Method in Solving Some Instances of the Subset Sum Problem.

Roman Kolpakov, Mikhail Posypkin

Open Comput. Sci., 2021

2020

The scalability analysis of a parallel tree search algorithm.

Roman Kolpakov, Mikhail Posypkin

Optim. Lett., 2020

Some results on the number of periodic factors in words.

Roman Kolpakov

Inf. Comput., 2020

2019

Optimal bounds for computing <i>α</i>-gapped repeats.

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov

Inf. Comput., 2019

2018

On the number of gapped repeats with arbitrary gap.

Roman Kolpakov

Theor. Comput. Sci., 2018

2017

Searching of gapped repeats and subrepetitions in a word.

Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin, Nickolay Khrapov

J. Discrete Algorithms, 2017

Complexity of solving the Subset Sum problem with the branch-and-bound method with domination and cardinality filtering.

Roman M. Kolpakov, Mikhail Posypkin, Si Tu Tant Sin

Autom. Remote. Control., 2017

2016

Indexing and querying color sets of images.

Djamal Belazzougui, Roman Kolpakov, Mathieu Raffinot

Theor. Comput. Sci., 2016

Optimal Bounds for Computing \alpha α -gapped Repeats.

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov

Proceedings of the Language and Automata Theory and Applications, 2016

2015

Upper bound on the number of steps for solving the subset sum problem by the Branch-and-Bound method.

Roman Kolpakov, Mikhail Posypkin

CoRR, 2015

Optimal searching of gapped repeats in a word.

Maxime Crochemore, Roman Kolpakov, Gregory Kucherov

CoRR, 2015

2013

Various improvements to text fingerprinting.

Djamal Belazzougui, Roman Kolpakov, Mathieu Raffinot

J. Discrete Algorithms, 2013

2012

On primary and secondary repetitions in words.

Roman Kolpakov

Theor. Comput. Sci., 2012

2011

On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters.

Roman Kolpakov, Michaël Rao

Theor. Comput. Sci., 2011

Linear pattern matching on sparse suffix trees

Roman Kolpakov, Gregory Kucherov, Tatiana Starikovskaya

CoRR, 2011

Pattern Matching on Sparse Suffix Trees.

Roman Kolpakov, Gregory Kucherov, Tatiana Starikovskaya

Proceedings of the First International Conference on Data Compression, 2011

2010

On maximal repetitions of arbitrary exponent.

Roman Kolpakov, Gregory Kucherov, Pascal Ochem

Inf. Process. Lett., 2010

2009

Searching for gapped palindromes.

Roman Kolpakov, Gregory Kucherov

Theor. Comput. Sci., 2009

2008

New algorithms for text fingerprinting.

Roman Kolpakov, Mathieu Raffinot

J. Discrete Algorithms, 2008

Faster Text Fingerprinting.

Roman Kolpakov, Mathieu Raffinot

Proceedings of the String Processing and Information Retrieval, 2008

2005

Space efficient search for maximal repetitions.

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov

Theor. Comput. Sci., 2005

Polynomial Time Checking for Generation of Finite Distributions of Rational Probabilities.

Roman Kolpakov

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2005

Real-Time Traversal in Grammar-Based Compressed Files.

Leszek Gasieniec, Roman M. Kolpakov, Igor Potapov, Paul Sant

Proceedings of the 2005 Data Compression Conference (DCC 2005), 2005

2004

Linear-time computation of local periods.

Jean-Pierre Duval, Roman Kolpakov, Gregory Kucherov, Thierry Lecroq, Arnaud Lefebvre

Theor. Comput. Sci., 2004

Criterion of generativeness of sets of rational probabilities by a class of Boolean functions.

Roman M. Kolpakov

Discret. Appl. Math., 2004

Real-Time String Matching in Sublinear Space.

Leszek Gasieniec, Roman M. Kolpakov

Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003

Finding approximate repetitions under Hamming distance.

Roman M. Kolpakov, Gregory Kucherov

Theor. Comput. Sci., 2003

mreps: efficient and flexible detection of tandem repeats in DNA.

Roman M. Kolpakov, Ghizlane Bana, Gregory Kucherov

Nucleic Acids Res., 2003

Classes of Binary Rational Distributions Closed under Discrete Transformations.

Roman Kolpakov

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2003

2000

Finding Repeats with Fixed Gap.

Roman M. Kolpakov, Gregory Kucherov

Proceedings of the Seventh International Symposium on String Processing and Information Retrieval, 2000

1999

On Repetition-Free Binary Words of Minimal Density.

Roman M. Kolpakov, Gregory Kucherov, Yuriy V. Tarannikov

Theor. Comput. Sci., 1999

Finding Maximal Repetitions in a Word in Linear Time.

Roman M. Kolpakov, Gregory Kucherov

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

On Maximal Repetitions in Words.

Roman M. Kolpakov, Gregory Kucherov

Proceedings of the Fundamentals of Computation Theory, 12th International Symposium, 1999

1997

Minimal Letter Frequency in n-th Power-Free Binary Words.

Roman M. Kolpakov, Gregory Kucherov

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1995

On the Complexity of Generation of Rational Numbers by Boolean Functions.

Roman M. Kolpakov

Fundam. Informaticae, 1995