Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

t-Spanners for metric space searching

The problem of Proximity Searching in Metric Spaces consists in finding the elements of a set which are close to a given query under some similarity criterion. In this paper we present a new methodology to solve this problem, which uses a t-spanner G′(V, E) as the representation of the metric database. A t-spanner is a subgraph G′(V, E) of a graph G(V, A), such that E  A and G′ approximates the shortest path costs over G within a precision factor t.

Our key idea is to regard the t-spanner as an approximation to the complete graph of distances among the objects, and to use it as a compact device to simulate the large matrix of distances required by successful search algorithms such as AESA. The t-spanner properties imply that we can use shortest paths over G′ to estimate any distance with bounded-error factor t.

For this sake, several t-spanner construction, updating, and search algorithms are proposed and experimentally evaluated. We show that our technique is competitive against current approaches. For example, in a metric space of documents our search time is only 9% over AESA, yet we need just 4% of its space requirement. Similar results are obtained in other metric spaces.

Finally, we conjecture that the essential metric space property to obtain good t-spanner performance is the existence of clusters of elements, and enough empirical evidence is given to support this claim. This property holds in most real-world metric spaces, so we expect that t-spanners will display good behavior in most practical applications. Furthermore, we show that t-spanners have a great potential for improvements.     

Resource estimation for heterogeneous computing

Code-profiling is the process of determining the types of codes found in a given heterogeneous task. Once this information is available, it is desirable to know how many processors are needed for each of the code types. In this paper, we propose two methods for estimating the minimum number of processors required for each of these code types. The first method involves making use of task compatibility graphs. We show that a task compatibility graph can be generated by analyzing certain compatible relations between task module pairs of a given task flow graph. We define the resource (processor) minimization problem therefore to be equivalent to finding the minimal number of cliques that cover the task compatibility graph, or to finding the minimal number of colors that color the vertices of its complement graph, called task conflict graph. We solve this problem using a greedy approach in O(¦V¦log¦V¦¦E¦) time, where ¦V¦ and ¦E¦ are the number of vertices and edges of the task compatibility graph. We further show that for three special types of task compatibility graphs, optimal solution can be obtained in polynomial time. The second method studied in this paper uses the Cluster-M methodology for estimating the minimum number of processors. Examples are shown to compare the estimated results obtained using different techniques.     

A linear time algorithm for maximum matchings in convex, bipartite graphs

The problem of determining the maximum matching in a convex bipartite graph, G = (V₁, V₂, E), is considered. It is shown that by using the appropriate data structures, the maximum matching problem can be efficiently transformed into an off-line minimum problem. Since the off-line minimum problem has been shown to be linear, the maximum matching in a convex bipartite graph can be determined in O(|V₁|) time.     

Constrained string editing

Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion, and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transforming X to Y using any arbitrary edit constraint involving the number and type of edit operations to be performed. An algorithm is presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithm requires O(¦X¦ ¦ Y¦min(¦ X¦,¦ Y¦)) time and space. The technique to compute the optimal transformation is also presented.     

Minimum cost source location problem with vertex-connectivity requirements in digraphs

Given a digraph (or an undirected graph) G=(V,E) with a set V of vertices v with nonnegative real costs w(v), and a set E of edges and a positive integer k, we deal with the problem of finding a minimum cost subset SV such that, for each vertex vV−S, there are k vertex-disjoint paths from S to v. In this paper, we show that the problem can be solved by a greedy algorithm in time in a digraph (or in time in an undirected graph), where n=|V| and m=|E|. Based on this, given a digraph and two integers k and ℓ, we also give a polynomial time algorithm for finding a minimum cost subset SV such that for each vertex vV−S, there are k vertex-disjoint paths from S to v as well as ℓ vertex-disjoint paths from v to S.     

Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard

Let G=(V,E) be an undirected graph and C a subset of vertices. If the sets B_r(v)∩C, vV (respectively, vVC), are all nonempty and different, where B_r(v) denotes the set of all points within distance r from v, we call C an r-identifying code (respectively, an r-locating-dominating code). We prove that, given a graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r.     

Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

On fast planning of suboptimal paths amidst polygonal obstacles in plane

The problem of planning a path for a point robot from a source point s to a destination point d so as to avoid a set of polygonal obstacles in plane is considered. Using well-known methods, a shortest path from s to d can be computed with a time complexity of O(n²) where n is the total number of obstacle vertices. The focus here is in

1. (a) planning paths faster at the expense of setting for suboptimal path lengths and

2. (b) performance analysis of simple and/or well-known suboptimal methods.

A method that enables a hierarchical implementation of any path planning algorithm with no increase in the worst-case time complexity, is presented; this implementation enables fast planning of simple paths. Then methods are presented based on the Voronoi diagrams, trapezoidal decomposition and triangulation, which compute (suboptimal) paths in O(n√log n) time with the preprocessing costs of O(n log n), O(n²) and O(n log n), respectively. Using existing navigational algorithms for unknown terrains, algorithms that run in O(n log n) time (after preprocessing) and yield suboptimal paths, are presented. For all these algorithms, upper bounds on the path lengths are estimated in terms of the shortest of the obstacles, etc.     

Fast adaptive PNN-based thresholding algorithms

Thresholding is a fundamental operation in image processing. Based on the pairwise nearest neighbor technique and the variance criterion, this theme presents two fast adaptive thresholding algorithms. The proposed first algorithm takes O((m−k)mτ) time where k denotes the number of thresholds specified by the user; m denotes the size of the compact image histogram, and the parameter τ has the constraint 1τm. On a set of different real images, experimental results reveal that the proposed first algorithm is faster than the previous three algorithms considerably while having a good feature-preserving capability. The previous three mentioned algorithms need O(m^k) time. Given a specific peak-signal-to-noise ratio (PSNR), we further present the second thresholding algorithm to determine the number of thresholds as few as possible in order to obtain a thresholded image satisfying the given PSNR. The proposed second algorithm takes O((m−k)mτ+γN) time where N and γ denote the image size and the fewest number of thresholds required, respectively. Some experiments are carried out to demonstrate the thresholded images that are encouraging. Since the time complexities required in our proposed two thresholding algorithms are polynomial, they could meet the real-time demand in image preprocessing.     

Uniform controllable sets of left-invariant vector fields on compact Lie groups

A set of vector fields on a differentiable manifold M is said to be uniformly completely controllable (u.c.c.) if there exists a nonnegative integer N such that evert pair (p, q) of point of M can be joined by a trajectory, or positive orbit, of which involves at most N switches.

In this article we show that if M is a Lie group G and a set of left-invariant vector fields on G, N must be greater than or equal to dim(G)-1. We also construct sets of vector fields which are uniformly completely controllable in dim(G)-1 switches when G is the Lie group of any compact real form of g and g runs over all classical simple Lie algebras over .     

Parallel algorithms for solving the satisfaction problem of functional and multivalued data dependencies

Parallel algorithms for solving the satisfaction problem of non-trivial functional and multivalued data dependencies (FDs and MVDs) in a relation of N tuples by M processors are developed in this paper. Algorithms performing, in a parallel manner, batch or interactive checking of these data dependencies are also discussed. The M processors are organized as a linear systolic array. The time complexities of the first two algorithms for solving the FD satisfaction problem under M N are both O(N), and that of Algorithm (3) or (4) for solving the FD or MVD satisfaction problem under N M is O(N²/M). The latter complexity reduced to O(N) if N = M and is at least not worse than O(N log N) if N = M (N/log N).     

M/G/c/K blocking probability models and system performance

An exact solution for the M/G/c/K model is only possible for special cases, such as exponential service, a single server, or no waiting room at all. Instead of basing the approximation on an infinite capacity queue as is often the case, an approximation based on a closed-form expression derivable from the finite capacity exponential queue is presented. Properties of the closed-form expression along with its use in approximating the blocking probability of M/G/c/K systems are discussed. Extensive experiments are provided to test and verify the efficacy of our approximate results.     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

Paired-domination in inflated graphs

The inflation G_I of a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique K_d. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γ_p(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)2, then n(G)γ_p(G_I)4m(G)/[δ(G)+1], and the equality γ_p(G_I) = n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.     

A multi-tree routing scheme using acyclic orientations

We propose a mathematical model for fault-tolerant routing based on acyclic orientations, or acorns, of the underlying network G=(V,E). The acorn routing model applies routing tables that store the set of parent pointers associated with each out-neighborhood defined by the acorn. Unlike the standard single-parent sink-tree model, which is vulnerable to faults, the acorn model affords a full representation of the entire network and is able to dynamically route around faults. This fault tolerance is achieved when using the acorn model as a multi-tree generator for gathering data at a destination node, as well as an independent tree generator for global point-to-point communication. A fundamental fault-tolerant measure of the model is the capacity of an acorn, i.e., the largest integer k such that each vertex outside the neighborhood N(v) of the destination v has at least k parent pointers. A capacity-k acorn A to destination v is k-vertex fault-tolerant to v. More strongly, we show A supports a k independent sink-tree generator, i.e., the parent pointers of each vertex w V−N(v) can be partitioned into k nonempty classes labeled 1,2,…,k such that any set of sink trees T₁,T₂,…,T_k are pairwise independent, where tree T_i is a sink tree generated by parent pointers labeled i together with the parent pointers into v. We present an linear time optimization algorithm for finding an acorn A of maximum capacity in graphs, based upon a minimax theorem. We also present efficient algorithms that label the parent pointers of capacity-k acorn A, yielding a k-independent sink tree generating scheme.     

Efficient and scalable quicksort on a linear array with a reconfigurable pipelined bus system

Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined abus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log₂ N) average time on a linear array with a reconfigurable pipelined bus system of size N. If the number of processors available is reduced to P, where P < N, the algorithm runs in O((N/P) log₂ N) average time and is still scalable. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.     

Finding hidden independent sets in interval graphs

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X?” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.