Zobrazeno 1 - 10
of 289
pro vyhledávání: '"GAWRYCHOWSKI, PAWEŁ"'
The classical pattern matching asks for locating all occurrences of one string, called the pattern, in another, called the text, where a string is simply a sequence of characters. Due to the potential practical applications, it is desirable to seek a
Externí odkaz:
http://arxiv.org/abs/2410.22109
Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindromes, the concatenation of palindromes of length greater than one, and th
Externí odkaz:
http://arxiv.org/abs/2410.03309
Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to the weighted case, where each output element has a weight and the output
Externí odkaz:
http://arxiv.org/abs/2409.18563
The task of min-plus matrix multiplication often arises in the context of distances in graphs and is known to be fine-grained equivalent to the All-Pairs Shortest Path problem. The non-crossing property of shortest paths in planar graphs gives rise t
Externí odkaz:
http://arxiv.org/abs/2408.04613
A permutation graph is the intersection graph of a set of segments between two parallel lines. In other words, they are defined by a permutation $\pi$ on $n$ elements, such that $u$ and $v$ are adjacent if an only if $u\pi(v)$. We con
Externí odkaz:
http://arxiv.org/abs/2407.12147
Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw [J. Algorithm
Externí odkaz:
http://arxiv.org/abs/2405.03856
A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct str
Externí odkaz:
http://arxiv.org/abs/2403.06667
In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outputting succinct representations of such walks, after a preprocessing s
Externí odkaz:
http://arxiv.org/abs/2401.02163
Given a signed permutation on $n$ elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomics, as it allows to accurately model rearrangements in small genomes. T
Externí odkaz:
http://arxiv.org/abs/2308.15928
The fundamental question considered in algorithms on strings is that of indexing, that is, preprocessing a given string for specific queries. By now we have a number of efficient solutions for this problem when the queries ask for an exact occurrence
Externí odkaz:
http://arxiv.org/abs/2304.00887