Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r×min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively.

In this paper, we define a new subclass of integer linear programming problems called the composition problem. We shall propose efficient algorithms for solving this problem and its variants. Moreover, as an application of the composition problem, those algorithms are applied to solve the P-constrained secure set problem, which is a variation of the secure set problem introduced in [5], on trees. A P-constrained secure set problem is to find a minimum secure set containing a set of |P| predetermined vertices.

In this paper, we propose a new class of graphs called generalized recursive circulant graphs which is an extension of recursive circulant graphs. While retaining attractive properties of recursive circulant graphs, the new class of graphs achieve more flexibility in varying the number of vertices. Some network properties of recursive circulant graphs, like degree, connectivity and diameter, are adapted to the new graph class with more concise expression. In particular, we use a multidimensional vertex labeling scheme in generalized recursive circulant graphs. Based on the labeling scheme, a shortest path routing algorithm for the graph class is proposed. The correctness of the routing algorithm is also proved in this paper.

A rotation in a binary tree is a local restructuring that changes the tree into another and preserves the inorder sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. However, a polynomial-time algorithm for computing rotation distances between any two binary trees has still not been found. Lucas (The Computer Journal, 47, 259–269, 2004) recently presented an O(n2)-time algorithm for finding the exact rotation distance between two binary trees that are of a restricted form (each node has at most one child in the source tree and there is at most one zig-zag pair in the destination tree), where n is the number of nodes in each binary tree. In this paper, by using the coding technique of left weight sequences, which was proposed by Pallo (The Computer Journal, 9, 171–175, 1986), we find another restricted set of binary trees in which any two of them can be transformed with the exact rotation distance. Our algorithm can be performed in linear time for finding the rotation distance between any two trees in the restricted set. Moreover, the actual sequence of transforming rotations can also be built.

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences.

Two spanning trees rooted at vertex r in a graph G are called independent spanning trees (ISTs) if for each vertex v in G, vner, the paths from vertex v to vertex r in these two trees are internally distinct. If the connectivity of G is k, the IST problem is to construct k ISTs rooted at each vertex. The IST problem has found applications in fault-tolerant broadcasting, but it is still open for general graphs with connectivity greater than four. In this paper, we shall propose a very simple algorithm for solving the IST problem on multidimensional torus networks. In our algorithm, every vertex can determine its parent for a specific independent spanning tree only depending on its own label. Thus, our algorithm can also be implemented in parallel systems or distributed systems very easily.

Abstract Jwo et al. [Networks 23 (1993) 315–326] introduced the alternating group graph as an interconnection network topology for computing systems. They showed that the proposed structure has many advantages over n‐cubes and star graphs. For example, all alternating group graphs are hamiltonian‐connected (i.e., every pair of vertices in the graph are connected by a hamiltonian path) and pancyclic (i.e., the graph can embed cycles with arbitrary length with dilation 1). In this article, we give a stronger result: all alternating group graphs are panconnected, that is, every two vertices x and y in the graph are connected by a path of length k for each k satisfying d(x, y) ≤ k ≤ |V| − 1, where d(x, y) denotes the distance between x and y, and |V| is the number of vertices in the graph. Moreover, we show that the r‐dimensional alternating group graph AGr, r ≥ 4, is (r − 3)‐vertex fault‐tolerant Hamiltonian‐connected and (r − 2)‐vertex fault‐tolerant hamiltonian. The latter result can be viewed as complementary to the recent work of Lo and Chen [IEEE Trans. Parallel and Distributed Systems 12 (2001) 209–222], which studies the fault‐tolerant hamiltonicity in faulty arrangement graphs. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 302–310 2004

A weighted double-loop network can be modeled by a directed graph G(n; h/sub 1/, h/sub 2/; w/sub 1/, w/sub 2/) with vertex set Z/sub n/={0, 1, ..., n-1} and edge set E=E/sub 1//spl cup/E/sub 2/, where E/sub 1/={(u, u+h/sub 1/)|u/spl isin/Z/sub n/}, E/sub 2/={(u, u+h/sub 2/)|u/spl isin/Z/sub n/}. Assume that the weight of each edge in E/sub 1/ is w/sub 1/ and the weight of each edge in E/sub 2/ is w/sub 2/. In this paper, we present an optimal routing algorithm on double-loop networks under the case where there is at most one faulty element. Our algorithm is based on the fact that the shortest path from a vertex to any other vertex in a double-loop network is in the L-shape region.

A tree T is labeled when the n vertices are distinguished from one another by names such as v/sub 1/, v/sub 2/...v/sub n/. Two labeled trees are considered to be distinct if they have different vertex labels even though they might be isomorphic. According to Cayley's tree formula, there are n/sup n-2/ labeled trees on n vertices. Prufer used a simple way to prove this formula and demonstrated that there exists a mapping between a labeled tree and a number sequence. From his proof, we can find a naive sequential algorithm which transfers a labeled tree to a number sequence and vice versa. However, it is hard to parallelize. In this paper, we shall propose an O(log n) time parallel algorithm for constructing a labeled tree by using O(n) processors and O(n log n) space on the EREW PRAM computational model.

A cross-bridge reconfigurable array of processors is a parallel processing system which has the ability to change dynamically the supported interconnection scheme during the execution of an algorithm. Based on this architecture, several O(1) time basic operations such as the transpose, the untranspose, the shift, the unshift and the prefix sum of a binary sequence are first proposed. Then, these basic operations can be used to find the kth smallest element of N m bits unsigned integers in O(m) time using N processors and to sort N data items in O(1) time using O(N/sup 5/3/) processors instead of using O(N/sup 2/) processors as those proposed by other researchers.>

In this paper, instead of using the base-2 number system, we use a base-m number system to represent the numbers used in the proposed algorithms. Such a strategy can be used to design an O(T) time, T=[log/sub m/N]+1, prefix sum algorithm for a binary sequence with N-bit on a cross-bridge reconfigurable array of processors using N processors, where the data bus is m-bit wide. Then, this basic operation can be used to compute the histogram of an n/spl times/n image with G gray-level value in constant time using G/spl times/n/spl times/n processors, and compute the Hough transform of an image with N edge pixels and n/spl times/n parameter space in constant time using n/spl times/n/spl times/N processors, respectively. This result is better than the previously known results. Also, the execution time of the proposed algorithms is tunable by the bus bandwidth.>

The authors consider upper bounds on the number of intersections between two rectangular paths. Let these two paths be denoted as P and Q, and denote the number of Manhattan subpaths in P and Q by mod P mod and mod Q mod respectively. K. Kant (1985) gave an upper bound of 10 mod P mod mod Q mod /9+4( mod P mod + mod Q mod )/9. The authors have sharpened these upper bounds, using methods to break the rectangular paths into subpaths, to be mod P mod mod Q mod +( mod P mod /2)+( mod Q mod /3), where they assume without loss of generality that mod P mod>