A \((p,q)\)-graph \( G \) is called \((a,d)\)-\({edge\; antimagic\; total}\), in short \((a,d)\)-EAMT, if there exist integers \( a > 0 \), \( d \geq 0 \) and a bijection \( \lambda: V \cup E \to \{1, 2, \ldots, p+q\} \) such that \( W = \{w(xy) : xy \in E\} = \{a, a+d, \ldots, a + (q-1)d\} \), where \( w(xy) = \lambda(x) + \lambda(y) + \lambda(xy) \) is the edge-weight of \( xy \). An \((a,d)\)-EAMT labeling \( \lambda \) of \( G \) is \({super}\), in short \((a,d)\)-SEAMT, if \( \lambda(V) = \{1, 2, \ldots, p\} \). In this paper, we propose some theorems on how to construct new (bigger) \((a, d)\)-SEAMT graphs from old (smaller) ones.

Let \( G = (V, E) \) be a graph with \( V(G) \) as a set of vertices and \( E(G) \) as a set of edges, where \( n = |V(G)| \) and \( e = |E(G)| \). A graph \( G = (V, E) \) is said to be \((a, d)\)-vertex antimagic total if there exist positive integers \( a \), \( d \), and a bijection \( \lambda \) from \( V(G) \cup E(G) \) to the set of consecutive integers \(\{1, 2, \ldots, n+e\}\) such that the weight of vertices forms an arithmetical progression with initial term \( a \) and common difference \( d \). In this paper, we will give \((a, d)\)-vertex antimagic total labeling of disconnected graphs, which consists of the union of \( t \) suns for \( d \in \{1, 2, 3, 4, 6\} \).

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.