For given graphs \( G \) and \( H \), the \({Ramsey\; number}\) \( R(G, H) \) is the least natural number \( n \) such that for every graph \( F \) of order \( n \) the following condition holds: either \( F \) contains \( G \) or the complement of \( F \) contains \( H \). In this paper, we determine the Ramsey number for a disjoint union of paths versus the cocktail party graph.

We study the complexity of the longest common subsequence (LCS) problem from a new perspective. By an indeterminate string (i-string, for short) we mean a sequence \( \tilde{X} = \tilde{X}[1]\tilde{X}[2]\ldots \tilde{X}[n] \), where \( \tilde{X}[i] \subseteq \Sigma \) for each \( i \), and \( \Sigma \) is a given alphabet of potentially large size. A subsequence of \( \tilde{X} \) is any usual string over \( \Sigma \) which is an element of the finite (but usually of exponential size) language \( \tilde{X}[i_1]\tilde{X}[i_2]\ldots \tilde{X}[i_p] \), where \( 1 \leq i_1 < i_2 < i_3 \ldots < i_p \leq n \), \( p \geq 0 \). Similarly, we define a supersequence of \( x \). Our first version of the LCS problem is Problem ILCS: for given i-strings \( \tilde{X} \) and \( \tilde{Y} \), find their longest common subsequence. From the complexity point of view, new parameters of the input correspond to \( |\Sigma| \), and maximum size \( \ell \) of the subsets in \( \tilde{X} \) and \( \tilde{Y} \). There is also a third parameter \( \mathcal{R} \), which gives a measure of similarity between \( \tilde{X} \) and \( \tilde{Y} \). The smaller the \( \mathcal{R} \), the lesser is the time for solving Problem ILCS. Our second version of the LCS problem is Problem CILCS (constrained ILCS): for given i-strings \( \tilde{X} \) and \( \tilde{Y} \) and a plain string \( Z \), find the longest common subsequence of \( \tilde{X} \) and \( \tilde{Y} \) which is, at the same time, a supersequence of \( Z \). In this paper, we present several efficient algorithms to solve both ILCS and CILCS problems. The efficiency in our algorithms is obtained in particular by using an efficient data structure for special types of range maxima queries and fast multiplication of boolean matrices.

We introduce a practical disk-based compressed text index that, when the text is compressible, takes much less space than the suffix array. It provides good I/O times for searching, which in particular improve when the text is compressible. In this aspect our index is unique, as most compressed indexes are slower than their classical counterparts on secondary memory. We analyze our index and show experimentally that it is extremely competitive on compressible texts. As side contributions, we introduce a compressed rank dictionary for secondary memory operating in one I/O access, as well as a simple encoding of sequences that achieves high-order compression and provides constant-time random access, both in main and secondary memory.

This paper introduces an automaton model called a dual position automaton (a dual PA), and then gives a bit-parallel algorithm for generating a dual PA from a regular expression (RE). For any RE \( r \) over an alphabet \( \Sigma \), our translation algorithm generates a dual PA consisting of \( \tilde{m}(\tilde{m} + 1) \) bits in \( O(\tilde{m}\lceil \tilde{m}/w \rceil) \) time and space, where \( w \) is the length of a computer word, \( \tilde{m} = \sum_{a \in \Sigma} m_a \), and \( m_a \) is the number of occurrences of an alphabet symbol \( a \) in \( r \). Furthermore, we give a method to construct a compact DFA representation from a dual PA. This DFA representation requires only \( (\tilde{m} + 1) \sum_{a \in \Sigma} 2^{m_a} \) bits. Finally, we show RE matching algorithms using such a DFA representation.

We investigate the problem of efficient representations of intervals of positive integers in TCAM (Ternary Content Addressable Memory). The integers are encoded by binary strings of the same length \( n \) and a TCAM of width \( n \) is a string-oriented representation of arbitrary sets of \( n \)-bit strings in terms of a collection of simple sets, called rules. Each rule is a concatenation (of length \( m \)) of singleton sets (i.e., single digits \( 0 \) and \( 1 \)) or the set \(\{0,1\}\) denoted by \( * \). We consider a family of \( n \)-bit encodings for integers, called dense-tree encodings, which includes the lexicographic encoding (i.e., standard unsigned binary encoding) and the binary reflected Gray encoding. We provide exact bounds (with respect to \( n \)) on the minimal sizes of TCAMs representing a subset of \( n \)-bit strings corresponding to an interval. Some other issues related to the minimal sizes and number of essential rules of TCAMs are also investigated.

This article develops an efficient combinatorial algorithm based on labeled directed graphs and motivated by applications in data mining for designing multiple classifiers. Our method originates from the standard approach described in [37]. It defines a representation of a multiclass classifier in terms of several binary classifiers. We are using labeled graphs to introduce additional structure on the classifier. Representations of this sort are known to have serious advantages. An important property of these representations is their ability to correct errors of individual binary classifiers and produce correct combined output. For every representation like this we develop a combinatorial algorithm with quadratic running time to compute the largest number of errors of individual binary classifiers which can be corrected by the combined multiple classifier. In addition, we consider the question of optimizing the classifiers of this type and find all optimal representations for these multiple classifiers.

A graph is called supermagic if it admits a labeling of its edges by consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper, we prove that the necessary conditions for an \( r \)-regular supermagic graph of order \( n \) to exist are also sufficient. All proofs are constructive and they are based on finding supermagic labelings of circulant graphs.

A distance magic labeling of a graph of order \( n \) is a bijection \( f: V \to \{1, 2, \dots, n\} \) with the property that there is a positive integer constant \( k \) such that for any vertex \( x \), \( \sum_{y \in N(x)} f(y) = k \), where \( N(x) \) is the set of vertices adjacent to \( x \). In this paper, we prove new results about the distance magicness of graphs that have minimum degree one or two. Moreover, we construct distance magic labeling for an infinite family of non-regular graphs.

Since Moore digraphs do not exist for \( k \neq 1 \) and \( d \neq 1 \), the problem of finding digraphs of out-degree \( d \geq 2 \), diameter \( k \geq 2 \) and order close to the Moore bound becomes an interesting problem. To prove the non-existence of such digraphs or to assist in their construction (if they exist), we first may wish to establish some properties that such digraphs must possess. In this paper, we consider the diregularity of such digraphs. It is easy to show that any digraph with out-degree at most \( d \geq 2 \), diameter \( k \geq 2 \) and order one or two less than the Moore bound must have all vertices of out-degree \( d \). However, establishing the regularity or otherwise of the in-degree of such a digraph is not easy. In this paper, we prove that all digraphs of defect two are either diregular or almost diregular. Additionally, in the case of defect one, we present a new, simpler, and shorter proof that a digraph of defect one must be diregular, and in the case of defect two and for \( d = 2 \) and \( k \geq 3 \), we present an alternative proof that a digraph of defect two must be diregular.

In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree \(d\) and \(d^2 + 1\) vertices), and found that such graphs exist only for \(d = 2, 3, 7\) and possibly \(57\). In 1980, Erdős et al., using eigenvalue analysis, showed that, with the exception of \(C_4\), there are no graphs of diameter 2, maximum degree \(d\) and \(d^2\) vertices. In this paper, we show that graphs of diameter 2, maximum degree \(d\) and \(d^2 – 1\) vertices do not exist for most values of \(d\) with \(d \geq 6\), and conjecture that they do not exist for any \(d \geq 6\).