Ionuţ Mugurel

Nicolae Andreica
email: nicolae.tapus@cs.pub.ro

Ţăpuş

New Algorithmic Approaches for Computing Optimal Network Paths with Several Types of QoS Constraints

Keywords:

The problem of efficiently delivering data within networks is very important nowadays, especially in the context of the large volumes of data which are being produced each year and of the increased data access needs of the users. Efficient data delivery strategies must satisfy several types of Quality of Service (QoS) constraints which are imposed by the data consumers. One possibility of achieving this goal (particularly in the case of in-order data transfers) is to choose a satisfactory network delivery path. In this paper we present novel algorithmic approaches for computing optimal network paths which satisfy several types of (QoS) constraints.

INTRODUCTION

Efficient delivery of data is an important issue nowadays, particularly in the context in which large amounts of data are produced, accessed and consumed every year. Moreover, data consumers impose stringent QoS constraints on the data delivery mechanism in order to consider it of a good enough quality. In the case of in-order data delivery, one possibility of satisfying the constraints is to choose an adequate network delivery path. In this paper we consider multiple constrained network path optimization problems, for which we present novel algorithmic solutions. In Section II we consider an approximate bicriteria optimal path problem. In Section III we present sensitivity analysis algorithms for several optimal path problems (and more). In Section IV we present novel solutions for several Hamiltonian and constrained coloralternating paths and cycles in graphs. In Section V we discuss related work and in Section VI we conclude.

II. APPROXIMATE BICRITERIA OPTIMAL PATH

We consider a directed graph G with n vertices and m edges. Each directed edge e from u(e) to v(e) has two nonnegative integer weights w 1 (e) and w 2 (e). We want to find a path from a source vertex s to a destination vertex t which minimizes the sum of the w 1 weights of the edges on the path, under the constraint that the sum of the w 2 edges of the path is at most B (at least B). A standard but inefficient solution to this problem consists of constructing a graph G' of pairs (i,j), where i is a vertex of G and j is an integer value between 0 and Bmax=the sum of all the w 2 weights of the edges of G. For every edge e from u to v we add Bmaxw 2 (e)+1 edges, from a vertex (u,j) to the vertex (u, j+w 2 (e)) (0≤j≤Bmax-w 2 (e)); each such edge has a weight equal to w 1 (e). We now only need to compute the shortest paths (using the weights of the edges of G') from (s,0) to all the other vertices. The answer to our problem is the minimum length of the shortest path from (s,0) to some (t,j), with j≤B (or j≥B). A much more efficient approach, albeit a heuristic one, is the following. We assign to every edge e of G a cost function c(e,x)=w 1 (e)+x•w 2 (e), where x is a parameter. We compute the shortest path from s to t using the newly assigned cost functions of the edges, for x=0 and we compute w 2 sum(0)=the sum of the w 2 weights of the edges on the path. If w 2 sum(0)≤B (and we are in the "at most B" case) or w 2 sum(0)≥B (and we are in the "at least B" case), then the shortest path at x=0 is the one we are looking for (because it minimizes the sum of the w 1 weights disregarding the w 2 weights; however, the sum of the w 2 weights of the edges on the path satisfies the constraints). Let's assume now that w 2 sum(0)>B and we are looking for the path from s to t minimizing the sum of the w 1 weights with the constraint that the sum of the w 2 weights is at most B. We notice that as the parameter x increases from 0 to +∞, the total sum of the w 2 weights on the shortest path from s to t (using the cost functions c(*,x)) decreases (although not strictly). In fact, we have that w 2 sum(x')≥w 2 sum(x'') if x'≤x''. At x=+∞, the influence of the w 1 weights is negligible. Thus, at x=+∞, we can consider c(e,x=+∞)=w 2 (e) for every edge e. Let w 2 sum(+∞) be the sum of the w 2 weights of the shortest path from s to t when x=+∞. If w 2 sum(+∞)>B then we have no solution. Otherwise, we will binary search the smallest value of x (between 0 and +∞) for which w 2 sum(x)≤B. The sum of the w 1 weights on the edges of the shortest path from s to t for the value of x we found in the binary search is the minimum possible sum of the w 1 weights on a path from s to t which satisfies the constraints and which can be found by this algorithm. Note that w 2 sum(x) is computed as follows. We compute the shortest path from s to t using the costs c(e,x) on the edges. Then, we find the edges composing the actual path and we let w 2 sum(x) be the sum of the w 2 weights of these edges. The time complexity is O((m+n•log(n))• log(x)) for arbitrary directed graphs and O((m+n)•log(x)) for directed acyclic graphs.

In the second case, when we want the sum of the w 2 weights to be at least B and w 2 sum(0)<B, we notice that as we decrease x from 0 towards -∞, the value of w 2 sum(x) increases, i.e. we have w 2 sum(x')≥w 2 sum(x'') if x'≤x''.

Unlike the previous case, we now have to handle negative edge weights. We will first need to find the minimum value of xmin for which the graph G with the edge costs c(e,xmin) does not contain a negative cost cycle (we can first check if G contains a negative cost cycle for x=-∞; note that c(e,x=-∞)=-w 2 (e)). If it doesn't, then we set xmin=-∞. Otherwise, we start with xm=-1 and, as long as the graph does not have negative cost cycles for x=xm, we multiply xm by any value c>1 (i.e. we set xm=c•xm; e.g. c=2). Then, we binary search xmin on the interval [xm,0]. After this, we compute w 2 sum(xmin). If w 2 sum(xmin)<B then we stop. Otherwise, we will binary search the largest value of x in the interval [xmin,0] for which w 2 sum(x)≥B. The sum of the w 1 weights on the shortest path from s to t in the graph with edge costs c(e,x) where x is the value found by the binary search is the minimum sum of the w 1 weights of a path from s to t which satisfies the constraints (and which can be found by this algorithm). The time complexity in this case is O(m•n•log(x)) for arbitrary directed graphs (because of the negative edge costs, we need to use algorithms like Bellman-Ford-Moore) or O((m+n)•log(x)) for acyclic directed graphs.

Notice that in the case of directed acyclic graphs we can also compute the path from s to t with maximum sum of the w 1 weights, such that the sum of the w 2 weights is at most B (at least B) with the same O((m+n)•log(x)) time complexity. We introduce the same edge costs and we compute w 2 sum(0) like before (except that we now run a longest path algorithm instead of a shortest path algorithm). If w 2 sum(0) satisfies the constraints, then the initial path we found is the optimal solution. Otherwise, if w 2 sum(0)>B (for the case "at most B"), we have the property that w 2 sum(x')≤w 2 sum(x'') for x'≤x''. Thus, we will find a value xmin<0 such that w 2 sum(xmin)≤B (the same way we found the value xmin previously). Then, we will binary search the largest value of x in the interval [xmin,0] such that w 2 sum(x)≤B. The longest path corresponding to this value of x is a near-optimal path for our problem. If, initially, we have w 2 sum(0)<B (for the case "at least B"), we will first find a value xmax>0 such that w 2 sum(xmax)≥B (we start with xmax=1 and we multiply it by c>1 until the condition is met). Then, we binary search the smallest value of x in the interval [0,xmax] for which w 2 sum(x)≥B. The longest path corresponding to this value of x is a (near) optimal path for our original problem.

An optimal path (with respect to the aggregation function aggf) from every vertex u to t in a directed acyclic graph in which every edge e and vertex v have a weight we(e) and wv(v) can be computed recursively, using memoization. We initialize the values computed(u)=false for every vertex u. We have popt(t)=wv(t) and computed(t)=true. Then, we consider every vertex u and we call Compute(u) which takes the following steps: (1) if computed(u)=false then: { (1.1) popt(u)=aggf(wv(u), opt{aggf(we(e), Compute(v)) | e is an edge directed from u to v}); (1.2) computed(u)=true; } (2) return popt(u). opt can be, for instance, max or min.

III. SENSITIVITY ANALYSIS ALGORITHMS

A. Classifying Graph Edges and Vertices

We consider a directed graph G, in which every directed edge (u,v) (from vertex u to vertex v) has a weight w(u,v).

We would like to classify the vertices and edges of this graph into 3 categories, relative to the shortest path (i.e. the path of minimum total weight) between two given vertices s and t: 1) belonging to every shortest path from s to t ; 2) belonging to at least one shortest path from s to t ; 3) belonging to no shortest path from s to t. We will start by computing the shortest path tree rooted at s (i.e. the shortest paths from s to every other vertex of the graph). We can achieve this in O(m+n•log(n)) time, where m is the number of edges of the graph and n is the number of vertices. Let ds(u) be the distance from s to u in the graph (if u is not reachable from s, then ds(u)=+∞). If ds(t)=+∞ then t is not reachable from s and all the edges and vertices belong to category 3 (as there is no path from s to t).

If ds(t)<+∞ then we compute the shortest path distances from t to every vertex of the graph, considering the transposed graph (i.e. the graph in which the direction of each edge is reversed). Let dt(u) be the distance from t to u in the transposed graph. We will mark the vertices u for which ds(u)+dt(u)=ds(t)(=dt(s)); the other vertices will be left unmarked. Note that s and t are also marked (as ds(s)=dt(t)=0 and ds(t)=dt(s)). Then, we construct the graph G' containing all the marked vertices and all the edges between them (an edge (u,v) is included in G' only if both u and v were marked). Every edge that was not included in G' and every vertex that was not marked belong to category 3. After this, we will ignore the direction of the edges of G', thus turning G' into an undirected graph G''. In G'' we will compute the bridges and cut vertices, in O(m+n) time. Every directed edge (u,v) from G' corresponding to a bridge in G'' belongs to category 1; every vertex from G' corresponding to a cut vertex in G'' also belongs to category 1. All the other edges and vertices from G' belong to category 2.

When the edge weights are all 1 (or all equal, in which case we can replace them by 1), we can improve the time complexity to O(m+n). The distances from s to every vertex of G and from t to every vertex of the transpose of G can be computed with a simple BFS traversal. Afterwards, we construct G' like before (again, all the edges and vertices outside of G' belong to category 3). After constructing G', we do not need to construct G'' anymore and compute its edges and cut vertices. Instead, we will initialize an array cnt (with indices from 0 to n-1) to 0. Then, for every vertex u of G' we increase cnt(ds(u)) by 1. cnt(d) will be equal to the number of vertices

u of G' such that ds(u)=d. A vertex u of G' belongs to category 1 only if cnt(ds(u))=1 (otherwise, if cnt(ds(u))>1, then u belongs to category 2). A directed edge (u,v) of G' belongs to category 1 only if both u and v belong to category 1; otherwise, (u,v) belongs to category 2.
The algorithms described in this section can also be used for undirected graphs. If we have an undirected graph UG, we will construct a directed graph G with the same vertices as UG, by adding to G two directed edges (u,v) and (v,u) for every undirected edge (u,v) of UG; both edges will have the same weight w(u,v). Then, we run one of the algorithms described above. A vertex of UG belongs to the same category as the corresponding vertex of G. An edge (u,v) of UG belongs to category 1 (2) if at least one of the edges (u,v) or (v,u) belongs to category 1 [START_REF] Andreica | An Algorithmic Perspective on Some Network Design, Construction and Analysis Problems[END_REF]. Note that if one of the edges (u,v) and (v,u) belongs to category 1 or 2, then the other edge belongs to category 3. An edge (u,v) of UG belongs to category 3 if both edges (u,v) and (v,u) of G belong to category 3.

B. Classifying Items Relative to Knapsack Solutions

We have n items. Each item i (1≤i≤n) has a weight w(i)≥0. We want to find a subset of items whose sum of weights is exactly S (the knapsack problem). We would like to classify the n items into 3 categories: 1) belonging to every knapsack solution; 2) belonging to at least one knapsack solution; 3) belonging to no solution. We will assume that we can afford O(n•S) time and memory. We will compute ok 1 (i,j)=true, if we can obtain the sum j using some of the items 1, …, i, or false, otherwise (0≤i≤n; 0≤j≤S). Moreover, we also compute cnt 1 (i,j)=the number of solutions for obtaining the sum j from the items 1, …, i (bounded from above at any value Q≥2, even Q=+∞; 0≤i≤n; 0≤j≤S). We have ok 1 (0,0)=true, cnt 1 (0,0)=1, ok 1 (0,1≤j≤S)=false and cnt 1 (0,1≤j≤S)=0. For 1≤i≤n (in this order) we have:

ok 1 (i,0≤j<min{w(i),S+1})=ok 1 (i-1,j), cnt 1 (i,0≤j<min{w(i), S+1})=cnt 1 (i-1,j)), ok 1 (i,w(i)≤j≤S)=ok 1 (i-1,j) or ok 1 (i-1, j- w(i))
(the first case considers that item i is not used for obtaining the sum j, while the second case considers that item i is used for obtaining the sum j) and cnt 1 (i,w(i)≤j≤S)= min{Q, cnt 1 (i-1,j)+cnt 1 (i-1,j-w(i))}. Then, in a similar manner, we compute ok 2 (i,j)=true, if we can obtain the sum j using some of the items i, i+1, …, n, or false, otherwise, and cnt 2 (i,j) (1≤i≤n+1; 0≤j≤S). We have ok 2 (n+1,0)=true, cnt 2 (n+1,0)=1, ok 2 (n+1,1≤j≤S)=false and cnt 2 (n+1,1≤j≤S)= 0. For 1≤i≤n (in decreasing order) we have: ok 2 (i,0≤j<min{w(i), S+1})=ok 2 (i+1,j), cnt 2 (i,0≤j<min{w(i), S+1})=cnt 2 (i+1,j), ok 2 (i,w(i)≤j≤S)=ok 2 (i+1,j) or ok 2 (i+1,jw(i)) and cnt 2 (i,w(i)≤j≤S)=min{Q, cnt 2 (i+1,j)+cnt 2 (i+1,jw(i))}. With these tables, we can decide for each item i in O(S) time to which category it belongs. We will compute c(i)=the sum of the values cnt 1 (i-1,j)•cnt 2 (i+1,S-j) (0≤j≤S), and d(i)=the logical OR of the values (ok 1 (i-1,j) and ok 2 (i+1,S-j-w(i))) (0≤j≤S-w(i); d(i)=false if w(i)>S). If d(i)=false then item i belongs to category 3; otherwise, if c(i)>0 then item i belongs to category 2 (there is at least one solution without item i) and if c(i)=0 then item i belongs to category 1 (there is no solution without item i, meaning that item i belongs to every knapsack solution).

Note how this solution is much better than the trivial solution which would remove every item i one at a time, would recompute the knapsack problem's dynamic programming tables every time (obtaining an O(n 2 •S) time complexity), and would compute a(i)=true (false) if the sum S-w(i) can (cannot) be obtained and b(i)=true (false) if the sum S can (cannot) be obtained. If a(i)=false then item i is in category 3; if a(i)=true and b(i)=true (b(i)=false) then item i is in category 2 (1).

We will now also assign a cost cost(i) to every item i and we want to find a subset of items whose sum of weights is equal to S and whose sum of costs is minimum. As before, we want to classify the items into the same 3 categories, relative to an optimal solution for this problem: 1) belonging to every optimal solution; 2) belonging to at least one optimal solution; 3) belonging to no optimal solution. We will compute cmin 1 (i,j) (cmin 2 (i,j)) = the minimum cost of a subset of the items 1, …, i (i, …, n) such that their sum of weights is j (0≤j≤S); we also compute cnt 1 (i,j) (cnt 2 (i,j)) = the number of subsets, bounded from above by any value Q≥2 (even Q=+∞), of the items 1, …, i (i, …, n) whose sum of weights is j and whose sum of costs is cmin 1 (i,j) (cmin 2 (i,j)) (0≤j≤S). We have cmin 1 (0,0)=cmin 2 (n+1,0)=0, cnt 1 (0,0)= cnt 2 (n+1,0)=1, cmin 1 (0,1≤j≤S)=cmin 2 (n+1, 1≤j≤S)=+∞, and cnt 1 (0,1≤j≤S)=cnt 2 (n+1,1≤j≤S)=0.

For 1≤i≤n (in increasing order) we have:

cmin 1 (i, 0≤j<min{w(i), S+1}) = cmin 1 (i-1,j), cnt 1 (i,0≤j<min{w(i), S+1})=cnt 1 (i-1, j), cmin 1 (i,w(i)≤j≤S)=min{cmin 1 (i-1,j), cmin 1 (i-1,j-w(i))+cost(i)}, and cnt 1 (i,w(i)≤j≤S)=min{Q, the sum of the values cnt 1 (i-1,j) and (if (cmin 1 (i-1, j- w(i))+cost(i)=cmin 1 (i,j)) then cnt 1 (i-1, j-w(i)) else 0)}.
Similarly, for 1≤i≤n (in decreasing order) we have: cmin 2 (i, 0≤j<min{w(i), S+1}) = cmin 2 (i+1,j), cnt 2 (i, 0≤j<min{w(i), S+1})=cnt 2 (i+1, j), cmin 2 (i, w(i)≤j≤S) = min{cmin 2 (i+1,j), cmin 2 (i+1, j-w(i))+cost(i)}, and cnt 2 (i, w(i)≤j≤S)=min{Q, the sum of the values cnt 2 (i+1,j) and (if (cmin 2 (i+1, jw(i))+cost(i)=cmin 2 (i,j)) then cnt 2 (i+1, j-w(i)) else 0)}. With these tables, we will decide for each item i into which category it belongs. If cmin 1 (n,S)=+∞ then all the items belong to category 3. Otherwise, for each item i, we will compute the following values: c(i)=the sum of the values cnt 1 (i-1,j)•cnt 2 (i+1,S-j) (where 0≤j≤S and cmin 1 (i-1,j)+cmin 2 (i+1,S-j)=cmin 1 (n,S)), and [START_REF] Young | Faster Parametric Shortest Path and Minimum-Balance Algorithms[END_REF] (n,S) then the item i belongs to category 3. Otherwise (if d(i)=cmin 1 (n,S)) then: if c(i)>0 then item i belongs to category 2, otherwise (if c(i)=0) then item i belongs to category 1.

d(i)=min{cmin 1 (i- 1,j)+cost(i)+cmin 2 (i+1,S-j-w(i)) | 0≤j≤S-w(i)} (if w(i)>S then d(i)=+∞). If d(i)>cmin

IV. HAMILTONIAN AND COLOR-ALTERNATING PATHS AND CYCLES

A. Hamiltonian Path in a Tournament Graph

We consider a tournament graph G (a directed graph in which there is exactly one directed edge between any two vertices i and j: either the edge i->j, or j->i) with n vertices. We want to find a Hamiltonian path in this graph. The graph is not given explicitly. Its structure can be discovered by asking questions: Ask(u,v) (u≠v) returns 1, if the edge u->v exists in the graph, or -1, if the edge v->u exists in G.

A tournament graphs always contains at least one Hamiltonian path. We can construct such a path incrementally. We will start with a path of length 1, consisting of the vertex 1. Then, we will traverse the other vertices i=2,…,n. When we reach the vertex i, we will already have a path v(1), …, v(i-1) composed of the vertices 1, …, i-1 (in some order), such that we have the directed edges v(j)->v(j+1) (1≤j≤i-2). If the edge i->v [START_REF] Young | Faster Parametric Shortest Path and Minimum-Balance Algorithms[END_REF] exists in G, then we can add the vertex i before v(1) and obtain a path with i vertices. If, instead, the edge v(i-1)->i exists in G, then we can add i after v(i-1) and obtain a path with i vertices. If none of the edges i->v [START_REF] Young | Faster Parametric Shortest Path and Minimum-Balance Algorithms[END_REF] and v(i-1)->i exist in G, then we will traverse the vertices v(j) on the path found so far (j=2,…,i-1), until we find the first vertex for which the edge i->v(j) exists in G. We will insert the vertex i between v(j-1) and v(j), obtaining a new path: v(1), …, v(j-1), i, v(j), …, v(i-1). The time complexity of this approach is O(n 2 ). Another O(n 2 ) solution is the following. We consider the vertices in the order p(1)=1, ..., p(i)=i, ..., p(N)=N. Then, we will repeatedly traverse these vertices. When we find two adjacent vertices p(i) and p(i+1) such that the edge between them is oriented from p(i+1) to p(i), then we swap the two vertices in the p ordering. When no more swaps can be performed, we stop. This algorithm is very similar to bubble-sort. The previous algorithm was very similar to the insertion sort method. The O(n 2 ) solutions presented earlier can be improved to O(n•log(n)). We will start by improving the first presented solution, as follows. Let's assume that we arrived at vertex i and we currently have a path v(1), …, v(i-1) (containing the vertices 1, …, i-1). We will find in O(log(n)) time the place where the vertex i will be inserted in the path. If we have the edge i->v( 1), then we add the vertex i before v(1); otherwise, if we have the edge v(i-1)->i then we add vertex i after v(i-1). Otherwise, we know that we have the edges v(1)->i and i->v(i-1). We will use the binary search technique and, at every step, we will maintain an interval [a,b], such that we have the edges v(a)->i and i->v(b). Initially, a=1 and b=i-1. Within the binary search, we will select c=(a+b) div 2. If we have the edge v(c)->i, then we maintain further the interval [c,b]; otherwise, we have the edge i->v(c) and we will maintain further the interval [a,c]. The binary search ends when b=a+1. Then, we insert vertex i between v(a) and v(a+1) in the path.

Other solutions with O(n•log(n)) time complexities are based on sorting algorithms like merge-sort or quick-sort. Basically, we consider that every vertex i of the graph has an associated value val(i). When running the sorting algorithms, we will try to sort the vertices in "increasing" order of their values. When we need to compare the values of two vertices i and j, we make the following decision:

• if we have the edge i->j then val(i)<val(j) • if we have the edge j->i then val(j)<val(i)

Although the tournament graph may contain cycles, the ordering produced by the sorting algorithms using the decision process described above sorts the graph vertices in an order v(1), …, v(n), such that we have the edges v(i)->v(i+1) (1≤i≤n-1).

B. Constrained Path/Cycle in a Small Graph

We consider a directed graph with n vertices, where n is not too large. Every directed edge e (directed from u(e) to v(e)) has a cost cm(e)≥0 and every vertex u has a cost cn(u)≥0. We want to find a path/cycle containing exactly Q vertices for which the aggregate agg of the edge and vertex costs is minimum. For Q=1 we simply choose the vertex u with the minimum value cn(u). For Q≥2 we will compute the values D min (i, S)=the minimum cost of a path ending at the vertex i and passing through every vertex from the set S (S is a subset of {1,...,n} and contains the vertex i) and through no other vertex; we will also compute C min (i,j,S)=the minimum cost of a path whose two endvertices are i and j (the path is directed from i to j) and passes through every vertex of the set S (S is a subset of {1,...,n} and contains the vertices i and j) and through no other vertex. We will consider the subsets S in increasing order of their cardinality |S| (from 1 to Q). We have D min (i, {i})=cn(i) and C min (i,i,{i})=cn(i). For |S|≥2, we will proceed as follows. D min (i,S) (with i ∈ S) is equal to cn(i) agg min{D min (j, S\{i})+cm(e) | e is an edge directed from a vertex j to the vertex i, 1≤j≤n, j≠i, j∈S\{i}). C min (i, j, S) is equal to min{U(i,j,S), V(i,j,S)}, where: U(i, j, S)=cn(j) agg min{C min (i, k, S\{j}) agg cm(e) | e is an edge directed from the vertex k to the vertex j, 1≤k≤n, k≠j, k∈(S\{j})} and V(i, j, S)=cn(i) agg min{Cmin(k, j, S\{i}) agg cm(e)|e is an edge directed from the vertex i to the vertex k, 1≤k≤n, k≠i, k ∈ (S\{i})} (actually, V(i,j,S) may always be considered +∞). The answer will be min{D min (i,S)|1≤i≤N, |S|=Q} (for the path case), respectively min{C min (i,j,S) agg cm(e) | e is an edge directed from j to i, 1≤i,j≤N, i≠j, |S|=Q}. The time complexity of the algorithm is O(n 2 •T(n,Q)) for the path case and O(n 3 •T(n,Q)) for the cycle case, where T(n,Q)= C(n,0)+C(n,1)+...+C(n,Q) (C(i,j)=combinations of i elements taken as j). When Q=n, T(n,n)=2 n . Note that the algorithm can be generalized as follows: only some subsets S of vertices are allowed to form the path/cycle; in this case, we simply iterate when computing the answer over the valid subsets S only.

C. Hamiltonian Path in the Cube of a Graph

The cube graph G 3 of an undirected graph G is the graph in which two vertices x and y are directly connected by an edge if their distance in G is at most 3. In order to find a Hamiltonian path in G 3 , we will first find a spanning tree T of G and then we will focus on finding a Hamiltonian path in T 3 . We will choose an arbitrary root vertex r for T and we will perform a DFS traversal of T starting from r. We consider the level of each node: level(r)=1 and level(i≠r)= level(parent(i))+1. While traversing the tree, we will construct the Hamiltonian path HP as follows. We start with an empty path HP. Then, during the traversal, when we first enter a vertex i and level(i) is odd, we add the vertex i at the end of HP (before traversing any of the other vertices in vertex i's subtree). After finishing traversing the entire subtree of a vertex i, if level(i) is even, then we add i at the end of HP. It is easy to notice that the distance in T between any two consecutive nodes in HP is at most 3: if they have the same level parity, the distance between them is 2 (they are either two sons of the same vertex or one of them is the grand-parent of the other); the distance between two consecutive vertices x and y from HP can also be 3, by considering the following scenariolevel(x) is even and we exit the subtree of the vertex x, we return to vertex x's grand-parent z and then we enter the vertex y which is one of z's sons; of course, the distance may also be 1.

D. Optimal Color Alternating Path

We consider a graph with n vertices and m directed edges. Each edge e is directed from u(e) to v(e), has a cost cost(e)≥0 and a color col(e) (e.g. label). The colors are numbered from 1 to C. Every vertex u also has a cost cn(u). We want to find a path from the vertex s to the vertex t whose aggregate cost is minimum (using the aggregation function agg) and such that any two consecutive edges on the path have different colors. The first solution consists of constructing a color-expanded graph, in which every node is a pair (i,k), meaning that we reached node i of the initial graph and the last used edge had color k. Normally, 1≤k≤C, but we will also consider the case k=0 for the vertex i=s. For every directed edge e of the original graph we add an edge from (u(e),k) to (v(e),col(e)) with the cost cost(e)+ cn(v(e)) (1≤k≤C; k may also be 0 when u(e)=s; k≠col(e)). We will now compute the tree of minimum aggregate paths starting from (s,0) in the color-expanded graph (considering costs only on the graph's edges). The minimum cost of a color-alternating path from s to t is cn(s) agg the minimum of the costs of reaching a vertex (t,k) (0≤k≤C). The colorexpanded graph has O(n•C) vertices and O(m•C) edges. Another possibility is the following. We will compute the minimum cost of a path from s to every other vertex i of the graph (let this value be C min (i)). We will also maintain Col min (i)=the color of the last edge on the optimal path from s to i. We also compute C min,2 (i)=the minimum cost of a path from s to i such that the color of its last edge is different from Col min (i); let the color of the last edge of the path denoted by C min,2 (i) be Col min,2 (i). If the graph is directed and acyclic, then we will first compute a topological sort. Then, we traverse the vertices i in the order of this sort. For a vertex i we will consider as candidate (Cost, Color) pairs the following values: (C min (u(e)) agg cost(e) agg cn(i), col(e)) (where v(e)=i and col(e)≠Col min (u(e))) and (C min,2 (u(e)) agg cost(e) agg cn(i), col(e)) (where v(e)=i and col(e)≠Col min,2 (u(e))). If i=s then C min (s)=cn(s), Col min (s)=0, C min,2 (s)=+∞ and Col min,2 (s)=0. For i≠s we initialize C min (i)=C min,2 (i)=+∞ and Col min (i)= Col min,2 (i)=0. For each candidate pair (Cost, Color): [START_REF] Young | Faster Parametric Shortest Path and Minimum-Balance Algorithms[END_REF] if Cost<C min (i) then: (i) and Cost<C min,2 (i) and Color≠Col min (i) then we set (C min,2 (i), Col min,2 (i))=(Cost, Color). If the graph is not acyclic, then we could use the Bellman-Ford-Moore shortest path algorithm. We initialize the computed values like before. Then, we insert the vertex s in a queue Q. While Q is not empty, we extract the vertex i from the front of Q and we process it. We consider all the edges e with u(e)=i. The pairs (C min (i) agg cost(e) agg cn(v(e)), col(e)) (if Col min (i)≠ col(e)) and (C min,2 (i) agg cost(e) agg cn(v(e)), col(e)) (if Col min,2 (i)≠col(e)) are candidate pairs for the vertex v(e). For each candidate pair we proceed as before. If at least one of the values C min (v(e)) or C min,2 (v(e)) changes as a result of these actions, then we (re)insert the vertex v(e) into Q (if it is not already there).

(1.1) if Color≠Col min (i) then we set (C min,2 (i), Col min,2 (i))=(C min (i), Col min (i)); (1.2) (C min (i), Col min (i))=(Cost, Color); (2) if Cost≥C min

E. Color Alternating Euler Cycle

We consider an undirected graph with n vertices and m edges. Every edge e (between u(e) and v(e)) has a color col(e). We want to find an Euler cycle in this graph such that any two edges which are consecutive on the cycle have different colors. At first, we will consider every vertex x of the graph, together with all the edges e adjacent to it. Let's assume that the edge identifiers are unique, between 1 and m. The edges adjacent to the vertex x will be considered in an arbitrary order: mu(x,j), with 1≤j≤deg(x) (where deg(x) denotes the degree of the vertex x and mu(x,j) is an edge identifier). Moreover, we will maintain a hash table Hx(x) associated to every vertex x, where we will introduce pairs of the form (key=mu(x,j), value=j). The only condition required for having a color alternating Euler cycle is for the graph to be connected, the degree of every vertex must be even, and the number of edges with the same color adjacent to any vertex x should be at most deg(x)/2. Next, we will assign to every edge mu(x,j) another edge mu(x,pair(x,j)), such that mu(x,j) and mu(x,pair(x,j)) have different colors (and also mu(x,pair(x, pair(x,j)))=mu(x,j)). In order to achieve this, let's consider the following problem. We have 2•P objects of different colors, such that there are at most P objects of the same color. We want to split the objects into pairs such that the two objects of a pair should have different colors. Let C be the total number of distinct colors assigned to the 2•P objects. We will renumber the colors from 1 to C. We traverse the objects and maintain a hash table H (initially empty) and a counter C (initially 0). For every color C' of an object, we first look the key C' up in H; if we find it there, then let col be the value associated to the key C' in H -we will replace the color C' of the object by the color col. If C' is not in H, then we increment C by 1, we add to H the pair (key=C', value=C) and then we replace the color C' of the object by the color C. After this, we will construct an array nob(col)=the number of objects having the color col (we initialize all the values of the array to 0; then, we traverse all the 2•P objects and, for every color col of an object, we increment nob(col) by 1). Then, we will sort the C colors col in non-increasing order, according to their nob(col) values (we will use count sort in order to sort all the C colors in O(C) time, or any other sorting algorithm, for O(C•log(C)) time). Let this order be col 1 , ..., col C . Then we sort the objects in the order Ob(1), ..., Ob(2•P), such that the objects with the color col i are located on consecutive positions, starting from the position nob(col 1 )+...+nob(col i- 1 )+1, and ending at the position nob(col 1 )+...+nob(col i ). We can perform this sort very easily, in O(P) time, by constructing some lists L(col)=the list with all the objects having the color col (1≤col≤C), which we will then concatenate in the order L(col 1 ), ..., L(col C ). The P pairs we will construct will contain the objects (Ob(i), Ob(P+i)) (1≤i≤P). It is obvious that two objects Ob(i) and Ob(P+i) cannot have the same color. Using the solution to this problem and considering as colored objects the edges adjacent to every vertex x, we can assign to every edge mu(x,j) another edge mu(x,pair(x,j)) (we will also have mu(x,pair(x,pair(x,j)))=mu(x,j)).

The second stage of the algorithm consists of incrementally constructing the Euler cycle, as follows. For each vertex x we will mark all the edges mu(x,j) adjacent to x which were added to the cycle so far (initially, all the edges are unmarked) and we will maintain an index muidx(x), representing the fact that all the edges mu(x,1), …, mu(x,muidx(x)) have already been added to the cycle (initially, muidx(*)=0). We will maintain a linked list with the graph vertices and edges in the order in which they occur on the cycle. Between every two list elements corresponding to the vertices of the cycle we will have a list element corresponding to the edge connecting the two vertices (for the case where we can have multiple edges between the same pair of vertices). Initially, we will only introduce in the list an element corresponding to the vertex 1 (we consider the vertices numbered from 1 to n). Then, we will traverse the list. Let's assume that we reached an occurrence of a vertex x within the list. While muidx(x)<deg(x) we will perform the following actions: (Step 1) if the edge mu(x, muidx(x)+1) has already been marked as belonging to the cycle, then we simply increment muidx(x) by 1; (Step 2) if the edge mu(x,muidx(x)+1) has not been marked as belonging to the cycle, then we will construct a cycle starting from this edge. Let's assume that this edge connects the vertex x to the vertex y. At first, we mark the edge mu(x, muidx(x)+1). Then, we set nodc=y and mprev=mu(x, muidx(x)+1) and we will construct the cycle as follows. While nodc≠x or the value associated to the edge mprev in Hx(x) is not pair(x,muidx(x)+1) then: (a) midxprev=the index (value) associated to the key mprev in Hx(nodc); (b) midxnext=pair(nodc, midxprev); (c) mnext=mu(nodc, midxnext); (d) we mark the edge mnext as belonging to the cycle; (e) the edge mnext connects the vertex nodc to another vertex z; (f) we set nodc=z and mprev=mnext. At the end of the cycle construction, we are back at vertex x, the first edge of the cycle is mu(x,muidx(x)+1) and the last edge of the cycle is mu(x,pair(x,muidx(x)+1)). We will construct this cycle as a linked list, too (which is initialized with the elements corresponding to the vertex x, the edge mu(x,muidx(x)+1), and then the vertex y; after every execution of the step (f) we add to the list an element corresponding to the edge mprev and then an element corresponding to the vertex nodc). We will try to replace the occurrence of the vertex x from the main cycle (the occurrence from which we started to construct the new cycle), by the newly constructed cycle. If x is the first vertex from the list corresponding to the main cycle, then we can realize this immediately. Otherwise, let m 1 and m 2 be the edges preceding and succeeding x in the list of the main cycle. If m 1 's color is different than the color of the edge mu(x,muidx(x)+1) and m 2 's color is different from that of the edge mu(x,pair(x,muidx(x)+1)), then we can replace the occurrence x by the list corresponding to the new cycle right away (we only need to adjust the linked list pointers in order to insert the new cycle within the list of the main cycle instead of the former occurrence of the vertex x). If the condition does not hold, then we can insert the new cycle in the main cycle list in reverse order: instead of the current occurrence of the vertex x in the main cycle list, we will insert the newly constructed cycle, but traversed in the other direction than the one in which it was constructed (i.e. in reverse order) -thus, in the main cycle, m 1 will be followed by the edge mu(x,pair(x,muidx(x)+1)) and the edge mu(x,muidx(x)+1) will be followed by the edge m 2 . After performing these actions we will consider that the current occurrence of the vertex x is the one corresponding to the first element of the newly constructed cycle. After this, we finished the execution of the Step 2 and we can go to the next iteration of the "while muidx(x)<deg(x)" loop.

V. RELATED WORK

Efficient algorithms for a parametric shortest path problem which is similar to the one we presented in Section II were given in [START_REF] Young | Faster Parametric Shortest Path and Minimum-Balance Algorithms[END_REF]. Sensitivity analysis algorithms for edges and vertices relative to matchings (in bipartite graphs) and minimum spanning trees were given in [START_REF] Andreica | An Algorithmic Perspective on Some Network Design, Construction and Analysis Problems[END_REF]. Algorithms for finding Hamiltonian paths in tournament graphs have been known for quite some time [START_REF] Balakrishnan | Schaum's Outline of Theory and Problems of Graph Theory[END_REF], but our approach describes multiple solutions and presents more details than in other publications. Hamiltonian paths and cycles in the cube of a tree were previously studied, for instance, in [START_REF] Bakker | Uniform d-Emulations of Rings, with an Application to Distributed Virtual Ring Construction[END_REF]. The novelty of our approach is the algorithm itself. The color alternating Euler cycle has also been studied before in [START_REF] Benkouar | On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-Colored Complete Graphs[END_REF], but they use there different methods for matching pairs of edges adjacent to the same vertex.

VI. CONCLUSIONS

In this paper we presented novel algorithmic techniques for several constrained optimal path problems in networks. We considered both bicriteria and single criterion optimization problems. We also developed efficient algorithms for the sensitivity analysis of network links and vertices. Many of the presented algorithms can be applied in real-life scenarios, in which the network parameters are not too dynamic.


Ionuţ Mugurel

Nicolae Andreica
email: nicolae.tapus@cs.pub.ro

Ţăpuş

Practical Algorithmic Techniques for Several String Processing Problems

Keywords: string processing, prefix query, trie, suffix array, KMP, deterministic finite automaton

The domains of data mining and knowledge discovery make use of large amounts of textual data, which need to be handled efficiently. Specific problems, like finding the maximum weight ordered common subset of a set of ordered sets or searching for specific patterns within texts, occur frequently in this context. In this paper we present several novel and practical algorithmic techniques for processing textual data (strings) in order to efficiently solve multiple problems. Our techniques make use of efficient string algorithms and data structures, like KMP, suffix arrays, tries and deterministic finite automata.

INTRODUCTION

Textual data exists and is constantly being produced in large amounts -web pages, digital libraries or official state documents all need to be processed efficiently in order to be able to extract automatically the information contained within them. Web search engines classify and store the text data into efficient data structures, data mining algorithms make use of similarities between multiple pieces of data, and biologists analyze large DNA sequences in order to extract information regarding genes and identify patterns. In this paper we present novel and practical algorithmic solutions for several string processing problems. Our techniques make use of efficient string algorithms and data structures, like KMP, suffix arrays, tries, deterministic finite automata, and others. In Section II we discuss two types of string prefix queries. In Section III we address the problem of optimally concatenating a set of strings, in order to optimize an objective metric. In Section IV we study constrained optimal length common subsequences and we present novel solutions for the shortest common contiguous non-subsequence of a set of strings. In Section V we construct and count strings having specific properties. Finally, in Section VI we discuss related work and in Section VII we conclude.

II. STRING PREFIX QUERIES

We consider a string S=c 1 c 2 …c n (of length n). We want to preprocess the string in order to be able to answer the following types of queries: 1) PQ(i,j)=is the prefix c 1 c 2 …c i of S equal to c j-i+1 c j-i+2 …c j ? (j≥i) ; 2) LPQ(j,k)=which is the largest value of i such that i≤k (0≤i≤k≤j) and PQ(i,j)=true ? The solution for both types of queries consists of first running the preprocessing stage of the Knuth-Morris-Pratt (KMP) algorithm [START_REF] Crochemore | Jewels of Stringology: Text Algorithms[END_REF]. As a result of this stage, the table p(i) is computed, where p(i) is the largest value (p(i)<i) such that PQ(p(i),i)=true. We will construct a tree having n+1 vertices (one for each prefix length of S: from 0 to n). The parent of the vertex i will be p(i). Vertex 0 will be the root of the tree. The two types of queries can be translated in terms of this tree (called the failure tree [START_REF] Gu | An Efficient Algorithm for Dynamic Text Indexing[END_REF]). PQ(i,j) returns true only if i is an ancestor of the vertex j (including j). The answer to LPQ(j,k) is the lowest ancestor i of vertex j such that i≤k. We will describe next efficient solutions for answering these ancestor queries. We perform a DFS traversal of the tree starting from the root (vertex 0). We assign to each vertex i its DFS number, DFSnum(i). During the traversal, we maintain a counter q (initially, q=0). When we first enter a vertex i, we increment q by 1 and then we set DFSnum(i)=q. When we exit a vertex i (after visiting its entire subtree) we set DFSmax(i)=q. A vertex i is an ancestor of a vertex j if DFSnum(i)≤DFSnum(j) and DFSmax(i)≥DFSmax (j).

In order to answer the second type of queries, we compute for each vertex i the values Anc(i,j)=the ancestor of vertex i which is located 2 j levels higher than i. Anc(i,0)= p(i) (Anc(root,0)=root) and Anc(i,j≥1)=Anc(Anc(i,j-1),j-1). Let's assume that every vertex v has a weight w(v) and we have w(v)≥w(p(v)) (in our case, we have w(v)=v). We can find the vertex v with the largest value w(v) which is an ancestor of a vertex i and such that w(v)≤k (we assume that such a vertex always exists; if not, we will return the root of the tree) in O(log(n)) time as follows. We set j=ceil(log 2 (n)) (we denote by ceil(x) the integer which is equal to x rounded up) and v=i. While j>0 do: (1) if (w(Anc(v,j))>k) then v=Anc(v,j); (2) j=j-1. In the end, if w(v)>k (and v is not the tree root) we set v=p(v). This approach has the disadvantage that it requires O(n•log(n)) memory. We can trade memory for running time, as follows. We will compute a value Anc(i)=an ancestor of vertex i which is located c levels higher than i (or the closest ancestor which is located on a level which is a multiple of c). While traversing the tree, we maintain the DFS stack Stk of vertices. When first entering a vertex i, this vertex is pushed at the top of the stack and when exiting a vertex i, this vertex is popped from the stack. Let's assume that the topmost level of the stack is ltop (the one containing vertex i). If ltop≤c we have Anc(i)=the tree's root; otherwise, we may set Anc(i)=Stk(ltop-c) or Anc(i)= Stk(ltop-1-((ltop-1) mod c)). Then, in order to find the ancestor v of vertex i with the largest weight w(v)≤k we proceed as follows. We initialize v=i. While (v is not the tree root) and w(Anc(v))>k we set v=Anc(v). Then, while (v is not the tree root) and (w(p(v))>k) we set v=p(v). In the end, if w(v)>k (and v is not the tree root) we set v=p(v).

III. OPTIMAL STRING CONCATENATIONS

A. Optimal Concatenation of Strings from Two Sets

We consider two sets A and B, each containing N strings. We want to compute the shortest string S which can be obtained as a concatenation of both some strings from A and of some strings from B. When considering the concatenation of the strings from each set, a string may occur zero, one, or multiple times. We will denote by len(x,y) the length of the string x from the set A (if y=1) or B (if y=2). We will conceptually construct two strings S 1 and S 2 , where S 1 is obtained by concatenating some strings from A and S 2 is obtained by concatenating some strings from B. Let's assume that, initially, S 1 contains a string from A and S 2 is empty. The algorithm for constructing the strings S 1 and S 2 will add a string from A (B) to S 1 (S 2 ) if S 1 (S 2 ) is shorter than S 2 (S 1 ). This way, the shorter string will always be a prefix of the longer string; the longer string may have some extra characters which are the suffix of a string from the corresponding set. We will compute the following table: L(i, j, p)=the minimum length of the shorter string (among S 1 and S 2 ), such that: (1) if p=1, then S 1 is longer than S 2 -S 1 has the structure S 2 +q (+ is concatenation), where q is the suffix of the string i from the set A, starting at the position j (0≤j≤len(i,1)) ; we consider the positions of the strings to be indexed starting from 0; (2) if p=2, then S 2 is longer than S 1 -S 2 has the structure S 1 +q, where q is the suffix of the string i from the set B, which starts at the position j (0≤j≤len(i,2))

We now have to solve a shortest path problem in a directed graph with O(N•(LMAX+1)) vertices (LMAX=the maximum length of a string from A or B), or O(sum of the lengths of all the strings from A and B). In order to compute the neighbors of a vertex (i,j,p), we will consider all the strings i 1 from the set A (if p=2) or B (if p=1). For every string i 1 , we will verify if this string matches the string i from the set A (if p=1) or B (if p=2), starting from the position j. Let's assume that the two strings match. Then, if len(i 1 ,3-p)≤len(i,p)-j, then the vertex (i,j,p) will have a directed edge towards the vertex (i, j+len(i 1 ,3-p), p) -the cost of this edge will be len(i 1 ,3-p); otherwise, the vertex (i, j, p) will have a directed edge towards the vertex (i 1 , len(i 1 , 3 -p) -len(i,p) + j, 3-p) -the cost of the edge will be (len(i,p)-j).

For every vertex (i,j,p) and every considered string i 1 we can test in O(LMAX) time if the string i 1 matches the corresponding suffix from the string i (starting at the position j). However, we can preprocess all this information using KMP. For each string i from A [p=1] (B [p=2]) we consider every string i 1 from B (A); we can compute in O(LMAX) time all the positions j from the string i at which the string i 1 may start such that it matches the suffix of the string i starting at j (j=j'-len(i 1 ,3-p)+1 if i 1 matches i on the positions j,…,j', or j=len(i,p)-j'', where j'' is the length of any prefix of i 1 which is an ancestor in i 1 's failure tree of the longest prefix of i 1 matching the end of i). Thus, we can test a match in O(1) amortized time for every tuple (i,j,p,i 1 ).

The graph has O(N•(LMAX+1)) vertices and O(N 2 • (LMAX+1)) (directed) edges. Using Dijkstra's algorithm, the time complexity is

O(N 2 •(LMAX+1) 2 ), or O(N 2 •(LMAX+1)• log(N•(LMAX+1)))) (if we use binary heaps), or O(N 2 • (LMAX+1)+N•(LMAX+1)•log(N•(LMAX+1)
)) (if we use Fibonacci heaps). At first, we will have L(*,0,*)=0 (the vertices (i,0,p) are the source vertices; we can always have multiple source vertices if we insert them all at the beginning in the queue/binary heap/Fibonacci heap) and L(*,j>0,*)= +∞. At the end of the algorithm, the length of the shortest string S that can be written as both a concatenation of strings from A and from B is min{L(i, len(i,p), p)}. The string S can be computed by tracing back the way we computed the values L(i,j,p) (starting from the vertex which minimizes the length of S). If we hadn't cared for finding the shortest string S with the given properties (and any string S would have been ok), then we could have simply traversed the constructed graph (using DFS or BFS), starting from the vertices (i,0,p) (we introduce all these vertices in the beginning in the BFS queue; in the DFS traversal case, we will start a new traversal from each such vertex, taking care not to traverse the vertices which were marked as traversed at previous DFS traversals or at the current DFS traversal). If we visit a vertex (i,len(i,p),p), then a string S with the given properties exists (and can be found by tracing back the path towards the source vertex/vertices). An application of this problem is the following. We have a set of strings A and we want to compute the shortest palindrome that can be obtained as a concatenation of some strings from the set (any string may be used zero, one, or multiple times). We will construct the set B as being formed of the strings from A, but reversed. Then, we will compute the same values as before. A vertex (i,j,p) denotes a solution if the substring starting at the position j from the string i of the set corresponding to p (A for p=1, and B for p=2) and ending at the end of the string is a palindrome (this substring may also have a length of 0 or 1). The answer will be min{2•L(i,j,p)+len(i,p)-j | the suffix of the string i from the set A (B) if p=1 (p=2), starting at the position j, is a palindrome}. The concatenation of the strings from the set B is reversed and attached at the end of the concatenation of the strings from A.

B. Minimum Lexicographic Concatenation

We consider N strings: S(1), …, S(N). We want to sort these strings in some order p(1), …, p(N), such that the string Q=S(p(1))+…+S(p(N)) (+ denotes the concatenation of two strings) is lexicographically minimum. Let len(X) be the length of the string X. We will use any sorting algorithm for sorting "increasingly" the N strings. When we need to compare two strings S(i) and S(j), we can decide that:

• if S(i)+S(j) < lex S(j)+S(i) then S(i) "<" S(j) • if S(i)+S(j) > lex S(j)+S(i) then S(i) ">" S(j) • if S(i)+S(j)=S(j)+S(i) then: if len(S(i))≤len(S(j)) then S(i) "≤" S(j) else S(i) ">" S(j)

IV. OPTIMAL LENGTH COMMON SUBSEQUENCES

A. Longest Common Contiguous Subsequence

We consider N strings: S(1), …, S(N). We want to compute the longest contiguous substring which occurs at least a(i) times (0≤a(i); 1≤i≤N) in at least F (0≤F≤N) strings among the N given (for the other strings S(i), the substring may occur fewer than a(i) times). We will construct a string Z=S(1) $ 1 S(2) $ 2 ... $ N-1 S(N), structured as follows: the string S(1), followed by the character $ 1 , then followed by S(2), then followed by $ 2 , ..., then followed by S(N). The characters $ 1 , ..., $ N-1 are distinct and they do not occur in any of the strings S(i) (1≤i≤N). We will construct a suffix array associated to Z, obtained by lexicographically sorting the suffixes of Z: su(1), ..., su(|Z|) (su(i) denotes the position of the first character from Z of the corresponding suffix; |Z|=len(Z)). For each suffix su(i) we know exactly to which string S(i) its first character belongs, because of its position in Z (the first |S(1)| positions are marked as belonging to S(1), the next position contains $ 1 , the next |S(2)| positions are marked as belonging to S(2), and so on); the suffixes for which the first character is one of the characters $ 1 , ..., $ N-1 will present no interest. We will also compute the values LCP(i)=the length of the longest common prefix of the suffixes su(i) and su(i+1) (1≤i≤|Z|-1). The suffix array and the array LCP can be constructed in O(|Z|•log(|Z|)) time. We will traverse the suffix array su(*) with two pointers, left and right. Initially, we will have left=1 and right=0. We will maintain an array x, where x(i)=the number of occurrences of a suffix whose starting position belongs to S(i), among the suffixes su(j) with left≤j≤right; initially, x(i)=0 (1≤i≤N). We will also maintain a counter nok=the number of strings S(i) for which a(i)≤x(i). Initially, nok is equal to the number of indices j for which a(j)=0 (1≤j≤N). If nok≥F from the start, then there are at least F values a(i)=0 and the answer is given by the string S(q) having the maximum length. Another particular case occurs when there are exactly F-1 values a(i) equal to 0, and the other values are at least 1 -in this case, the maximum length subsequence is the string S(k) with the maximum length such that a(k)≥1. After removing the special cases, we will perform |Z| steps. At the beginning of every step we will set right=right+1. If the suffix su(right) belongs to a string S(j), then we will set x(j)=x(j)+1; if x(j) becomes equal to a(j), then we set nok=nok+1. Then, we will increment the variable left by 1 as long as one of the following conditions is true: (1) the first position of the suffix su(left) belongs to no string S(j) (i.e. it corresponds to a character $ q ); (2) the first position of su(left) belongs to a string S(j) for which ((x(j)>a(j)) or ((x(j)=a(j)) and (nok>F))) : in this case we decrement x(j) by 1 first (and, if x(j) becomes smaller than a(j), we also decrement nok by 1) and only after this will we increment left by 1. After the (possible) changes of the variable left, we check if nok≥F. If it is, then we will compute the value W=min{LCP(j) | left≤j≤right-1} (if left=right, then W=the length of the suffix su(left), i.e. |Z|-su(left)+1; if the first character of su(left) is a $ q character, then W=-∞). We can compute these values in O(1) time, using the Range Minimum Query (RMQ) technique, which requires a simple O(|Z|•log(|Z|)) time preprocessing (or a more complicated O(|Z|) time one). W is the length of the longest substring of the strings S(i) which satisfies the constraints, considering only the suffixes on the positions left, left+1, …, right. We compare W with the largest length L found so far and we set L=max{W,L} (initially, L=0). Finally, after all these operations, we can skip to the next step

B. Longest Common Non-Contiguous Subsequence

We consider K strings: S(1), …, S(K), composed of characters from an alphabet with N symbols (numbered from 1 to N); each position j of a string S(i) has a weight wp(i,j)≥0. A string A is a (not necessarily contiguous) subsequence of another string B if it can be obtained from B by erasing 0 or more characters from B. We want to compute a string S which is a common subsequence of all the K given strings and whose aggregate weight is maximum. The weight of a string is computed as an aggregate function agg 1 of the weights of its characters. The weight of a character on a position of the string is equal to an aggregate agg 2 of the weights of the positions in which the character matches each of the K given strings; agg 1 is a non-decreasing function, defined for non-negative values (e.g., addition, max); agg 2 may be any function returning non-negative values (e.g. sum, multiplication, max, min). Each character i occurs num(j,i)≥1 times in S(j) (otherwise, we could remove the character from the alphabet and from every string which contains it). We know that the total number of tuples of positions (p 1 , ..., p k ), such that S(1)(p 1 )=S(2)(p 2 )=...=S(K)(p K ) is at most PMAX. The positions of a string are numbered starting from 1.

We will generate all the tuples (p(1), ..., p(K)) such that S(1)(p(1))=...=S(K)(p(K)). In order to do this, we will traverse every string S(i) and, for every character j, we will construct a list L(i,j) (initially, all these lists are empty). As we traverse the string S(i) and we reach the character on a position q, we insert q at the end of the list L(i,S(i)(q)). Thus, the elements of each list are added in increasing order. Then, we will generate all the tuples we mentioned, in lexicographic order. We will traverse, one at a time, the positions q(1) from S(1). For every position q(1) we will consider, in order, every position q(2) from L(2, S(1)(q(1))); for every pair (q(1), q(2)) we consider, in order, every position q(3) from L(3, S(1)(q(1))), and so on, for every tuple (q(1), …, q(r)) (with r<K) we traverse all the positions q(r+1) from L(r+1, S(1)(q(1))). Every time q(K) takes a value, we generate a new tuple (q(1), …, q(K)). The tuples are generated in lexicographic order. Every tuple (q(1), …, q(K)) will have an associated weight w(q(1), …, q(K))=agg 2 (wp(1,q(1)), …, wp(K,q(K))). Then, we will traverse the tuples in the order we generated them and we will maintain a (K-1)-dimensional range tree. For every tuple (p(1), …, p(K)), we will compute a weight wmax(p(1), …, p(K))=agg 1 (w(p(1), …, p(K)), max{wmax(p'(1), …, p'(K)) | 1≤p'(i)<p(i) for every 1≤i≤K}). In order to compute wmax(p(1), …, p(K)), we will use the range tree for computing the maximum weight of a point (p'(2), …, p'(K)) in the range tree (with p'(j)<p(j) for every 2≤j≤K); if no such point exists, the range tree will return the neutral value for the agg 1 function (e.g. 0 for sum, 1 for multiplication, -∞ for max). After traversing all the tuples (p(1), *, …, *) (i.e. with the same value of p( 1)), we insert into the range tree a point (p(2), …, p(K)), with the weight wmax(p(1), …, p(K)), for each such tuple (p(1), …, p(K)); these points will be considered when computing wmax(*, …, *) for the next tuples. A point insertion and a (range) query can be performed in O(log K-1 (PMAX)) time. Since all the points are known from the beginning, we can construct the range tree from the start for all the points, assigning to them weights equal to the neutral value of agg 1 . Then, a point insertion will consist of changing the weight of a point in the range tree. However, the time complexities stay the same.

The final time complexity is O(PMAX•log K-1 (PMAX)). The maximum weight of a common (non contiguous) subsequence of the K strings is max{wmax(p(1), ..., p(K))}.

Another interpretation of the problem is that we have a graph with O(PMAX) vertices; each vertex corresponds to a tuple (p(1), ..., p(K)). We have a directed edge from (p'(1), ..., p'(K)) to (p(1), ..., p(K)) if p'(i)<p(i) (for every 1≤i≤K). Each vertex (p(1), ..., p(K)) has a weight w(p(1), ..., p(K)).

In this directed acyclic graph we need to find a path with maximum aggregate weight (using the agg 1 function).

C. Shortest Common Contiguous Non-Subsequence

Given a set of R strings, St(1), …, St(R), we want to find the shortest string PS which is not a contiguous subsequence of any of the R given strings. The strings' characters belong to an alphabet A. The characters of PS must belong to the same alphabet A (the characters of A are numbered from 1 to |A|). Obviously, such a string always exists, because we can always choose a string longer than any string St(i). In [START_REF] Rubinov | String Noninclusion Optimization Problems[END_REF], the authors simply mentioned that the problem can be solved in polynomial time and presented a trivial (but suboptimal solution) based on sorting all the R strings. If |A|=1 then len(PS)=1+max{len(St(i))|1≤i≤R}. Otherwise, for every two consecutive strings in the sorted order, say St(F) and St(G), we compute the shortest string PS(F,G) which is located between St(F) and St(G) in lexicographic order. In order to do this, we need to compute LCP(F,G)=the length of the longest common prefix of St(F) and St(G). Then,

PS(F,G) is constructed as follows: we take the prefix of length LCP(F,G) of St(F) and then: let c 1 = St(F)(LCP(F,G)+1) and c 2 =St(G)(LCP(F,G)+1). We will consider St(F)(y)=0, if y>len(St(F)) and St(G)(y)=|A|+1, if y>len(St(G)).

If c 1 +1≤c 2 -1 then we add to PS(F,G) any character labeled with a number lb form the interval [c 1 +1,c 2 -1]. If, however, c 1 +1=c 2 , then we have two possibilities (and we will choose the one which leads to a shorter string). The first possibility occurs if c 1 >0. We add to PS(F,G) the character c 1 . Then, we need to compute the number of consecutive characters equal to |A| in St(F), starting from position LCP(F,G)+2. Let x=cnt(F, |A|, LCP(F,G)+2) be this number. We add to PS(F,G) x characters |A| and then we add a character which is larger than St(F)(LCP(F,G)+2+x). The second possibility occurs if c 2 ≤|A|. We add to PS(F,G) the character c 2 . Then, we need to compute the number of consecutive characters equal to 1 in St(G), starting from position LCP(F,G)+2. Let x=cnt(G, 1, LCP(F,G)+2) be this number. We add to PS(F,G) x characters 1 and then we add a character which is smaller than St(G)(LCP(F,G)+2+x). We can tabulate the cnt(*,*,*) values as follows. For y>len(St(U)) we have cnt(U, c, y)=0; for 1≤y≤len(St(U)) we have: if (St(U)(y)=c) then cnt(U, c, y)=1+cnt(U, c, y+1); otherwise, cnt(U, c, y)=0. For completeness, we add an empty virtual string at the beginning of the sorted order and an empty string at the end of the sorted order. We can implement all these operations in O(N•log(N)) time using the suffix arrays technique (N=the sum of the lengths of the R given strings, plus R-1): we construct a large string S=ST [START_REF] Gu | An Efficient Algorithm for Dynamic Text Indexing[END_REF]

$ 1 St(2) $ 2 … $ R-1 St(R),
where $ 1 , …, $ R-1 are different characters which are not part of A. Then, we can sort all the suffixes of S in O(N•log(N)) time and compute the longest common prefix (LCP) of any two consecutive suffixes in the sorted order in O(log(N)) time (by storing auxiliary information). Afterwards, we will maintain only the suffixes starting at the initial position of a string ST(i) and truncated, such that they do not contain $ j characters. We can compute the LCP between any pair of suffixes in the original order by using the Range Minimum Query (RMQ) technique on the array of LCP values between consecutive suffixes in the sorted order; the length of the LCP between two truncated suffixes is reduced if it exceeds the length of any of them. Another method for computing the LCP of two suffixes starting at any positions a and b of S was mentioned to us by C. Negruşeri. We will compute a hash value h(i) for every position i of S: h(0)=0 and h(1≤i≤N)=hash(h(i-1), S(i), i). With these values, we will be able to efficiently compute a hash value for any (contiguous) substring S(i:j) (from the position i to j) of S. The hash values of two substrings with the same value will be identical. Then, we will binary search the LCP between 0 and N-max{a,b}+1. We have LCP≥L if hashValue(a, a+L-1)=hashValue(b, b+L-1) (with a high probability) and LCP<L otherwise. We can use h(i)=(P 1 i-1 •S(i)+h(i-1)) mod P 2 andhashValue(i,j)=((((h(j)-h(i-1)+P 2 ) mod P 2 )•P 1

-(i-1)
) mod P 2 , where P 1 and P 2 are two prime numbers and P 1 -1 is the modular multiplicative inverse of P 1 modulo P 2 . After finding P 1 -1 , we will compute and store the values P 1

-i =(P 1 - (i-1)
•P 1 -1 ) mod P 2 for 2≤i≤N. We will present next a much simpler O(N•log(N)) solution. One of the simplest solutions that comes to mind is to try every possible length L (starting from 1) and, for each length L, generate all the |A| L strings of length L. For each generated string, we verify if it is contained in the constructed string S (in O(L+N) time, using the KMP or Rabin-Karp methods). The time complexity of this solution is O(N•|A| len(PS)+1 ). Let's notice first that PS cannot be too long. In order to have len(PS)=L, the string S must contain all the strings composed of L-1 characters. The shortest string S' (with characters from the alphabet A) which contains all the strings composed of Q characters can be constructed using the following (well-known) algorithm. We construct a graph which contains a vertex for every string composed of Q-1 characters. From every vertex i we have |A| outgoing (directed) edges. The qe th such edge is labeled with character qe (1≤qe≤|A|). In order to find the vertex j into which this edge enters, we proceed as follows.

Let SQ(i) be the Q-1 character string associated to vertex i. We add character qe at the end of SQ(i) (obtaining the string SQ'(i,qe)) and then we keep only the last Q-1 characters of SQ'(i,qe) (obtaining the string SQ''(i,qe)). Vertex j will be that vertex with SQ(j)=SQ''(i,qe). In this graph, every vertex has the in-degree and the out-degree equal to |A|. We will compute an Euler cycle in this graph (as the graph is also connected). This cycle will contain all the |A| Q edges of the graph (there are |A| Q-1 vertices, each of which has outdegree and in-degree |A|). In order to generate a string S' which contains all the strings composed of Q characters, we will choose an edge of the Euler cycle, which will be removed form the cycle. Then, we traverse the cycle starting from the next edge, until we reach the edge preceding the removed edge (at this moment, the entire cycle was traversed). For every traversed edge, we add its label at the end of S' (initially S' is empty). Let's assume that the removed edge was entering vertex j. Then we append at the beginning of S' the string SQ(j). Thus, S' has |A| Q +Q-1 characters. From the previously described algorithm we conclude that in order for the string S to contain all the strings composed of L characters, its length must be at least |A| L +L-1. Thus, L=O(log |A| (N)) and the initial algorithm has a time complexity of O(N•|A| log(N)+1 )=O(N 2 ). However, the time complexity is too large. In order to reduce it, we will construct a trie (prefix tree), where we will add all the contiguous subsequences of the sequence S, composed of L=log |A| (N)+1 characters. Building the trie takes O(N•log(N)) time. Afterwards, we remove from the trie all the edges (parent(q),q) marked with $ j characters (and the subtrees rooted at these vertices q). Then, we will traverse all the nodes in the trie. Let's assume that we reached a node q, located on level lev (0≤lev≤L-1). If node q does not have |A| sons, then we found a string composed of lev+1 characters which is not included in S. This string is composed of the labels on the edges on the path from the root of the trie to node q, to which we add a character c from A, such that none of the edges connecting node q to one of its sons is labelled with c. PS will be the shortest string found this way. This stage of the algorithm takes O(M) time, where M=O(N•log(N)) is the number of nodes in the trie.

V. CONSTRUCTING AND COUNTING STRINGS WITH SUBSTRING OCCURRENCE CONSTRAINTS

We consider an alphabet A with M characters, numbered from 1 to M. We are also given two lists L 1 and L 2 of strings composed of characters from the alphabet A. For each string S(i) from L 2 we are also given a set Occ(i) containing nonnegative numbers not larger than K. We are interested in counting the total numbers of strings SL of a length Len∈SLen with characters from the alphabet A such that:

• none of the strings from L 1 occurs as a contiguous substring in SL • the number o(i) of occurrences of each string S(i) from L 2 into SL is a number from Occ(i); two occurrences of the same string S(i) may partially overlap. We will start by constructing the deterministic finite automaton (DFA) of the strings from L 1 ∪ L 2 , like in [4].

Each state of the DFA which corresponds to the ending of a string from L 1 is marked as forbidden; the other states are not forbidden. For each non-forbidden state q we will compute the set SE(q) of the string indices i from L 2 such that the state q corresponds to matching the ending of the string i. We can do this like in [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF], where they use the concept of output links.

By following the output links starting at the state q, we will identify all the strings i whose ending matches the state q in O(|SE(q)|) time. We will now run a dynamic programming algorithm on the DFA. For each non-forbidden state q of the DFA and every tuple (o( 1 ). In the initial state q 0 (which we assume it is not forbidden) of the DFA (corresponding to a void string) we have Cnt(q 0 , 0, o(1)=0, …, o(i)=0, …, o(|L 2 |)=0)=1 and for every other state q≠q 0 we have Cnt(q, 0, o(1)=*, …, o(|L 2 |)=*)=0. We will compute these values in increasing order of l (1≤l≤max{Len|Len ∈ SLen}). For each non- forbidden state q we will initialize Cnt(q, l, o(1)=*, …, o(i)=*, …, o(|L 2 |)=*)=0. Then, we will consider all the directed edges entering q from other non-forbidden states q'. For each such state q' we will consider all the possible tuples (o(1), …, o(|L 2 |)) and we will increment Cnt(q, l, o(1)+x(q,1), …, o(i)+x(q,i), …, o(|L 2 |)+x(q,|L 2 |)) by the value Cnt(q', l-1, o(1), …, o(|L 2 |)). We have x(q,i)=1 if i∈SE(q) and 0, otherwise (1≤i≤|L 2 |). The final result is the sum of the values Cnt(q, Len, o(1), … o(|L 2 |)) of the nonforbidden states q, where Len ∈ SLen and o(i) ∈ Occ(i)

(1≤i≤|L 2 |). The time complexity is O(Lmax•K |L2| •(V+E)),
where Lmax=max{Len|Len ∈ SLen}, V is the number of states of the DFA and E is the number of edges of the DFA. A slightly more general problem is the following. We are given a DFA (with non-forbidden states only), in which we have an initial state and a set of final states (the initial state may also be final). We want to compute the number of strings of a length Len∈SLen that are accepted by the DFA (i.e. starting from the initial state and following the transitions corresponding to the characters of the string, we reach a final state). Moreover, some edges q->q' do not make us move to the next character of the string (i.e. they are non-absorbing). Every state q stores 4 lists of adjacent edges, for the following cases: incoming/outgoing and absorbing/non-absorbing. Moreover, within each list, it stores M sub-lists, one for each character of the alphabet (sub-list c contains the edges marked with c from the corresponding list). At first, we will process the DFA. For every character c from the alphabet, we consider DFA'(c)=the DFA containing all the states but only the nonabsorbing edges marked with c. From each state q there is at most one outgoing edge marked with c. We will identify the cycles in DFA'(c) and remove from DFA and DFA'(c) all the edges which are part of a cycle in DFA'(c). In order to identify the cycles, we consider that all the states are unmarked. Then, we consider every state q of DFA'(c). If q is unmarked, we move along the edges, starting from the one going out of q (if any) and mark all the states we visit. If we get back to q, then we found a cycle. After removing these edges, DFA'(c) is a directed acyclic graph. We will compute a topological sort of DFA'(c): ts(c,1), …, ts(c,V), such that all the states q' for which there is an edge q'->q (directed from q' to q) are located before q in the topological sort. Then, we will compute Cnt(q,l)=the number of strings of length l which can make the DFA reach the state q. We have Cnt(q 0 ,0)=1 and Cnt(q≠q 0 ,0)=0 (q 0 =the initial state). Then, for l=1,…,Lmax we perform the following steps: (1) for every character c we consider the states ts(c,1), …, ts(c,V) (in this order): we compute Cnt'(ts(c,i),l,c) as Cnt(ts(c,i),l-1) plus the sum of the values Cnt'(ts(c,j),l,c) (such that there is a non-absorbing edge marked with c from ts(c,j) to ts(c,i));

(2) we consider every state q and set Cnt(q,l) to the sum of the values Cnt'(q',l,c) (where q' is a state such that there is an absorbing directed edge from q' to q marked with the character c). The final answer is the sum of the values Cnt(q,Len), where q is a final state and Len∈SLen.

We will now consider a problem which is very similar to the first problem from this section. We are given the same input data, except that every string i from L 2 also has a weight w(i). We want to construct a string SL with maximum weight, which obeys the same constraints from the previous problem. The weight of a string SL is the aggregate agg of the weights of each occurrence of a string S(i) from L 2 into SL. Additionally, for some of the strings S(j) from L 2 we do not care how many times they occur in SL. We will proceed as follows. At first, we compute the DFA of all the strings from L 1 ∪ L 2 and we mark the forbidden states (as before).

Then, for each non-forbidden state q, we compute ws(q)=the aggregate agg of the weights w(i) of the strings i from L 2 which are part of SE(q). After this, we remove from L 2 and from all the sets SE(*) those strings i for which we don't care how many times they occur in the optimal string SL. After removing these strings, we will renumber the remaining strings from 1 to |L 2 | (we modify accordingly the numbering in L 2 and in every set SE(*)). Then, we will run a dynamic programming algorithm which is very similar to the one from the first problem. We will compute Wmax(q, l, o(1), …, o(|L 2 |))=the maximum weight of a string SL of length l whose suffix matches the string associated to the state q of the DFA and in which every (remaining) string i from L 2 occurs o(i) times and in which none of the strings from L 1 occur. We have Wmax(q 0 ,0,o(1)=…=o(|L 2 |)=0)=0 and -∞ for all the other tuples with l=0. For each length l from 1 to Lmax (in increasing order) we consider all the non-forbidden states q. We initialize Wmax(q, l, o(1)=*, …, o(|L 2 |)=*)=-∞ and Prev(q, l, o(1)=*, …, o(|L 2 |)=*)=undefined. Then, we consider all the directed edges entering q from other non-forbidden states q'. For each such state q' we consider all the tuples (q', l-1, o(1), …, o(|L 2 |)) such that Wmax(q', l-1, o(1), …, o(|L 2 |))>-∞ and if agg(Wmax(q', l-1, o(1), …, o(|L 2 |)), ws(q))>Wmax(q, l, o(1)+x(q,1), …, o(i)+x(q,i), …, o(|L 2 |)+x(q,|L 2 |)) then we set Wmax(q, l, o(1)+x(q,1), …, o(i)+x(q,i), …, o(|L 2 |)+x(q,|L 2 |))=agg(Wmax(q', l-1, o(1), …, o(|L 2 |)), ws(q)) and Prev(q, l, o(1)+x(q,1), …, o(i)+x(q,i), …, o(|L 2 |)+x(q,|L 2 |))=q'. In the end, we will compute wm=max{Wmax(q, Len, o( 1 (2) the character on the position Len of SL is the character on the directed edge from q' to q ; (3) o(i)=o(i)-x(q,i) (1≤i≤|L 2 |) ; (4) q=q' ; (5) Len=Len-1.

VI. RELATED WORK

The failure tree produced by the KMP algorithm was mentioned in [START_REF] Gu | An Efficient Algorithm for Dynamic Text Indexing[END_REF], but was not used directly as it is. In [START_REF] Rubinov | String Noninclusion Optimization Problems[END_REF], the authors studied several non-substring and nonsubsequence problems, focusing on whether they belong to the P or NP class. They also gave a trivial, but inefficient polynomial algorithm for the shortest non-contiguous subsequence problem, while we presented an efficient solution. String concatenations are related to the shortest common supersequence problem [START_REF] Blum | Linear Approximation of Shortest Superstrings[END_REF]. A survey of longest common subsequence algorithms (of only two strings) was presented in [START_REF] Bergroth | A Survey of Longest Common Subsequence Algorithms[END_REF]. The algorithms and data structures we used in this paper (e.g. KMP, trie, deterministic finite automaton) are well presented in several text books, like [START_REF] Gusfield | Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology[END_REF] and [START_REF] Crochemore | Jewels of Stringology: Text Algorithms[END_REF].

VII. CONCLUSIONS AND FUTURE WORK

In this paper we presented new and practical algorithmic solutions for several string processing problems which are important in the automatic knowledge extraction and data mining fields. Our solutions make use of several standard, but efficient, algorithmic techniques and data structures. The presented algorithms can easily be implemented in many data mining and knowledge discovery applications.

  . The time complexity of the entire algorithm is O(|Z|•log(|Z|)) (the preprocessing stage takes O(|Z|•log(|Z|)) time; all the other |Z| steps take O(|Z|) time overall).

  ), …, o(|L 2 |))| Len ∈ SLen ando(i)∈ Occ(i) (1≤i≤|L 2 |)}. If wm>-∞ then let (q, Len, o(1), …, o(|L 2 |)) be a tuple such that Wmax(q, Len, o(1), …, o(|L 2 |))=wm. We will construct the string from the end towards the front. While Len>0 do: (1) let q'=Prev(q, Len, o(1), …, o(|L 2 |)) ;

  SL of length l such that their suffix matches the string corresponding to the state q and each string i from L 2 occurs o(i) times in SL (|L 2 | denotes the number of strings in L 2 ; the strings from L 2 are numbered from 1 to |L 2 |

	), …, o(|L 2 |)) (with 0≤o(i)≤K;
	1≤i≤|L 2 |) we will compute Cnt(q, l, o(1), …, o(|L 2 |))=the
	total number of strings