Counting occurrences of some subword patterns.
Detecting the morphic images of a word : improving the general algorithm
Deux problèmes d'analyse d'algorithmes
Domination Game: Extremal Families for the 3/5-Conjecture for Forests
In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107]...
Dynamic programming for reduced NFAs for approximate string and sequence matching
searching for all occurrences of a pattern (string or sequence) in some text, where the pattern can occur with some limited number of errors given by edit distance. Several methods were designed for the approximate string matching that simulate nondeterministic finite automata (NFA) constructed for this problem. This paper presents reduced NFAs for the approximate string matching usable in case, when we are interested only in occurrences having edit distance less than or equal to a given integer,...
Efficient string matching on packed texts
e-Nets and Simplex Range Queries.
Estimation of tolerance relation on the basis of multiple pairwise comparisons with random errors
Evaluating scientific products by means of citation-based models: a first analysis and validation.
Exact and asymptotic distributions in digital and binary search trees
Extremum-searching hierarchical parallel probabilistic algorithms
Graph fibrations, graph isomorphism, and PageRank
PageRank is a ranking method that assigns scores to web pages using the limit distribution of a random walk on the web graph. A fibration of graphs is a morphism that is a local isomorphism of in-neighbourhoods, much in the same way a covering projection is a local isomorphism of neighbourhoods. We show that a deep connection relates fibrations and Markov chains with restart, a particular kind of Markov chains that include the PageRank one as a special case. This fact provides constraints on the...
Halfspace Range Search: An Algorithmic Application of k-Sets.
Heuristic search algorithms on directed trees
Large File Operations Support Using Order Preserving Perfect Hashing Functions
Linear Space Data Structures for Two Types of Range Search.
Minimum common string partition problem: hardness and approximations.
Multidimensional term indexing for efficient processing of complex queries
The area of Information Retrieval deals with problems of storage and retrieval within a huge collection of text documents. In IR models, the semantics of a document is usually characterized using a set of terms. A common need to various IR models is an efficient term retrieval provided via a term index. Existing approaches of term indexing, e. g. the inverted list, support efficiently only simple queries asking for a term occurrence. In practice, we would like to exploit some more sophisticated...
New Applications of Random Sampling in Computational Geometry.
Noise effects in the quantum search algorithm from the viewpoint of computational complexity
We analyse the resilience of the quantum search algorithm in the presence of quantum noise modelled as trace preserving completely positive maps. We study the influence of noise on the computational complexity of the quantum search algorithm. We show that it is only for small amounts of noise that the quantum search algorithm is still more efficient than any classical algorithm.