Minimizing Makespan in Batch Machine Scheduling

We study the scheduling of a set of n jobs, each characterized by a release (arrival) time and a processing time, for a batch processing machine capable of running at most B jobs at a time. We obtain an O(n log n)-time algorithm when B is unbounded. When there are only m distinct release times and the inputs are integers, we obtain an O(n(BR_max)^m-1(2/m)^m-3)-time algorithm where R_max is the difference between the maximum and minimum release times. When there are k distinct processing times and m release times, we obtain an O(n log m + k^k+2 B^k+1 m² log m)-time algorithm. We obtain even better algorithms for m=2 and for k=1. These algorithms improve most of the corresponding previous algorithms for the respective special cases and lead to improved approximation schemes for the general problem.     

An efficient algorithm for row minima computations on basicreconfigurable meshes

A matrix A of size m×n containing items from a totally ordered universe is termed monotone if, for every i, j, 1⩽i2. In case m=n^ϵ for some constant ϵ, (0<ϵ⩽1), our algorithm runs in O(log log n) time     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

A Faster and More Space-Efficient Algorithm for Inferring Arc-Annotations of RNA Sequences through Alignment

The nested arc-annotation of a sequence is an important model used to represent structural information for RNA and protein sequences. Given two sequences S₁ and S₂ and a nested arc-annotation P₁ for S₁, this paper considers the problem of inferring the nested arc-annotation P₂ for S₂ such that (S₁, P₁) and (S₂, P₂) have the largest common substructure. The problem has a direct application in predicting the secondary structure of an RNA sequence given a closely related sequence with known secondary structure. The currently most efficient algorithm for this problem requires O(nm³) time and O(nm²) space where n is the length of the sequence with known arc-annotation and m is the length of the sequence whose arc-annotation is to be inferred. By using sparsification on a new recursive dynamic programming algorithm and applying a Hirschberg-like traceback technique with compression, we obtain an improved algorithm that runs in min{O(nm² + n²m),O(nm² log n), O(nm³)} time and min{O(m² + mn), O(m² log n + n)} space.     

Scheduling unit-time tasks with integer release times and deadlines

The problem of scheduling n unit-time tasks with integer release times and deadlines is shown to be solvable in o(n log n) time if a sufficient amount of uninitialized space is available. Specifically, the tasks may be scheduled in O(f(n)) time, using O(M + n) space, where f(n) is the time to solve an off-line minimum problem, and M is the size of the largest deadline. By a recent result of Gabow and Tarjan (1983), f(n) is O(n).     

Geometry Helps in Bottleneck Matching and Related Problems

Let A and B be two sets of n objects in \reals ^d , and let Match be a (one-to-one) matching between A and B . Let min(Match ), max(Match ), and Σ(Match) denote the length of the shortest edge, the length of the longest edge, and the sum of the lengths of the edges of Match , respectively. Bottleneck matching— a matching that minimizes max(Match )— is suggested as a convenient way for measuring the resemblance between A and B . Several algorithms for computing, as well as approximating, this resemblance are proposed. The running time of all the algorithms involving planar objects is roughly O(n ^1.5 ) . For instance, if the objects are points in the plane, the running time of the exact algorithm is O(n ^1.5 log n ) . A semidynamic data structure for answering containment problems for a set of congruent disks in the plane is developed. This data structure may be of independent interest. Next, the problem of finding a translation of B that maximizes the resemblance to A under the bottleneck matching criterion is considered. When A and B are point-sets in the plane, an O(n ⁵ log n) -time algorithm for determining whether for some translated copy the resemblance gets below a given ρ is presented, thus improving the previous result of Alt, Mehlhorn, Wagener, and Welzl by a factor of almost n . This result is used to compute the smallest such ρ in time O(n ⁵ log ² n ) , and an efficient approximation scheme for this problem is also given. The uniform matching problem (also called the balanced assignment problem, or the fair matching problem) is to find Match ^* _U , a matching that minimizes max (Match)-min(Match) . A minimum deviation matching Match ^* _D is a matching that minimizes (1/n)Σ(Match) - min(Match) . Algorithms for computing Match ^* _U and Match ^* _D in roughly O(n ^10/3 ) time are presented. These algorithms are more efficient than the previous O(n ⁴ ) -time algorithms of Martello, Pulleyblank, Toth, and de Werra, and of Gupta and Punnen, who studied these problems for general bipartite graphs. Received October 21, 1997; revised July 16, 1998.     

Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

This paper presents an optimal sequential and an optimal parallel algorithm to compute a minimum cardinality Steiner set and a Steiner tree. The sequential algorithm takes O ( n ) time and parallel algorithm takes O (log n ) time and O ( n /log n ) processors on an EREW PRAM model.     

A Simple and Fast Min-Cut Algorithm

We present an algorithm which calculates a minimum cut and its weight in an undirected graph with nonnegative real edge weights, n vertices and m edges, in time O(max(log n, min(m/n,δ_G/ε)) n²), where ε is the minimal edge weight, and δ_G is the minimal weighted degree. For integer edge weights this time is further improved to O(δ_G n²) and O(λ_G n²). In both cases these bounds are improvements of the previously known best bounds of deterministic algorithms. These were O(nm + n² log n) for real edge weights and O(nM + n²) and O(M + λ_G n²) for integer weights, where M is the sum of all edge weights.     

A probabilistic analysis of an error-correcting algorithm for the towers of Hanoi puzzle

Let S be a set of n horizontal and vertical segments on the plane, and let s, t ∈ S. A Manhattan path (of length k) from s to t is an alternating sequence of horizontal and vertical segments, s = r₀, r₁,…,r_k = t, such that r_i intersects r_i+1, 0 ? i < k. An O(n log n) time O(n log n) space algorithm is presented which, given S and t, finds a tree of shortest Manhattan paths from all s ∈ S to t. The algorithm relies on a new data structure which makes it possible to find in O(log n + p) time all p segments currently in S which intersect a given s ∈ S, and which support a deletion of any segment from S in O(log n) time, where we assume that the cost of these operations is accumulated over the whole algorithm. The structure makes use of the recently discovered Gabow and Tarjan's linear time version of the union-find algorithm on consecutive sets. We prove an Ω(n log n) lower bound on the complexity of deciding whether there is a Manhattan path between two given segments, under the linear decision tree model. Finally, some applications of the Manhattan path algorithm are indicated.     

An optimal algorithm for shortest paths on weighted interval and circular-arc graphs,with applications

We give the first linear-time algorithm for computing single-source shortest paths in a weighted interval or circular-arc graph, when we are given the model of that graph, i.e., the actual weighted intervals or circular-arcsand the sorted list of the interval endpoints. Our algorithm solves this problem optimally inO(n) time, wheren is the number of intervals or circular-arcs in a graph. An immediate consequence of our result is anO(qn + n logn)-time algorithm for the minimum-weight circle-cover problem, whereq is the minimum number of arcs crossing any point on the circle; then logn term in this time complexity is from a preprocessing sorting step when the sorted list of endpoints is not given as part of the input. The previously best time bounds were0(n logn) for this shortest paths problem, andO(qn logn) for the minimum-weight circle-cover problem. Thus we improve the bounds of both problems. More importantly, the techniques we give hold the promise of achieving similar (logn)-factor improvements in other problems on such graphs.The research of M. J. Atallah was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the Air Force Office of Scientific Research under Contract AFOSR-90-0107, and by the National Science Foundation under Grant CCR-9202807. D. Z. Chen's research was supported in part by the Leonardo Fibonacci Institute, Trento, Italy. The research of D. T. Lee was supported in part by the Leonardo Fibonacci Institute, Trento, Italy, by the National Science Foundation, and the Office of Naval Research under Grants CCR-8901815, CCR-9309743, and N00014-93-1-0272.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

Minimum Dominating Sets of Intervals on Lines

We study the problem of computing minimum dominating sets of n intervals on lines in three cases: (1) the lines intersect at a single point, (2) all lines except one are parallel, and (3) one line with t weighted points on it and the minimum dominating set must maximize the sum of the weights of the points covered. We propose polynomial-time algorithms for the first two problems, which are special cases of the minimum dominating set problem for path graphs which is known to be NP-hard. The third problem requires identifying the structure of minimum dominating sets of intervals on a line so as to be able to select one that maximizes the weight sum of the weighted points covered. Assuming that presorting has been performed, the first problem has an O(n) -time solution, while the second and the third problems are solved by dynamic programming algorithms, requiring O(n log n) and O(n + t) time, respectively. Received April 13, 1995; revised July 27, 1996.     

An Optimal Parallel Co-Connectivity Algorithm

In this paper we consider the problem of computing the connected components of the complement of a given graph. We describe a simple sequential algorithm for this problem, which works on the input graph and not on its complement, and which for a graph on n vertices and m edges runs in optimal O(n+m) time. Moreover, unlike previous linear co-connectivity algorithms, this algorithm admits efficient parallelization, leading to an optimal O(log n)-time and O((n+m)log n)-processor algorithm on the EREW PRAM model of computation. It is worth noting that, for the related problem of computing the connected components of a graph, no optimal deterministic parallel algorithm is currently available. The co-connectivity algorithms find applications in a number of problems. In fact, we also include a parallel recognition algorithm for weakly triangulated graphs, which takes advantage of the parallel co-connectivity algorithm and achieves an O(log² n) time complexity using O((n+m²) log n) processors on the EREW PRAM model of computation.     

A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem

We consider a convex, or nonlinear, separable minimization problem with constraints that are dual to the minimum cost network flow problem. We show how to reduce this problem to a polynomial number of minimum s,t-cut problems. The solution of the reduced problem utilizes the technique for solving integer programs on monotone inequalities in three variables, and a so-called proximity-scaling technique that reduces a convex problem to its linear objective counterpart. The problem is solved in this case in a logarithmic number of calls, O(log U), to a minimum cut procedure, where U is the range of the variables. For a convex problem on n variables the minimum cut is solved on a graph with O(n²) nodes. Among the consequences of this result is a new cut-based scaling algorithm for the minimum cost network flow problem. When the objective function is an arbitrary nonlinear function we demonstrate that this constrained problem is solved in pseudopolynomial time by applying a minimum cut procedure to a graph on O(nU) nodes.     

Some Aperture-Angle Optimization Problems

Abstract. Let P and Q be two disjoint convex polygons in the plane with m and n vertices, respectively. Given a point x in P , the aperture angle of x with respect to Q is defined as the angle of the cone that: (1) contains Q , (2) has apex at x and (3) has its two rays emanating from x tangent to Q . We present algorithms with complexities O(n log m) , O(n + n log (m/n)) and O(n + m) for computing the maximum aperture angle with respect to Q when x is allowed to vary in P . To compute the minimum aperture angle we modify the latter algorithm obtaining an O(n + m) algorithm. Finally, we establish an Ω(n + n log (m/n)) time lower bound for the maximization problem and an Ω(m + n) bound for the minimization problem thereby proving the optimality of our algorithms.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Finding maximum cliques on circular-arc graphs

An algorithm is presented that, given the intersection model S of a circular-arc graph G with n vertices and m edges, finds a maximum-sized clique of G in O(n² log log n) time. The previous best time bound for this problem was O(n²) log n + mn).     

Deterministic Communication in Radio Networks with Large Labels

We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers) of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is raised and a deterministic broadcasting algorithm is proposed, which runs in O(n²log n) time for N polynomially large in n. The O(nlog²n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic O(n log N log n)-time broadcasting and O(n²log²N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically, we propose: a deterministic O(n^3/2log²N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log²N log²n)-time gossiping algorithm for undirected networks.     

Fast Spatial Decomposition and Closest Pair Computation for Limited Precision Input

In this paper we show that if the input points to the geometric closest pair problem are given with limited precision (each coordinate is specified with O( log n) bits), then we can compute the closest pair in O(n log log n) time. We also apply our spatial decomposition technique to the k -nearest neighbor and n -body problems, achieving similar improvements. To make use of the limited precision of the input points, we use a reasonable machine model that allows ``bit shifting' in constant time—we believe that this model is realistic, and provides an interesting way of beating the Ω(n log n) lower bound that exists for this problem using the more typical algebraic RAM model. Received October 12, 1998; revised October 26, 1998.