Polynomial algorithms for a class of minimum rank-two cost path problems

In this paper, we develop two algorithms for finding a directed path of minimum rank-two monotonic cost between two specified nodes in a network with n nodes and m arcs. Under the condition that one of the vectors characterizing the cost function f is binary, one yields an optimal solution in O(n³) or O(nm log n) time if f is quasiconcave; the other solves any problem in O(nm + n ² log n) time.     

Testing Homotopy for Paths in the Plane

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For paths specified by n line segments with obstacles described by n points, several standard ways achieve quadratic running time. For simple paths, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcrofts problem; our algorithm runs in O(n ^3/2log n) time.     

Gossip is synteny: Incomplete gossip and the syntenic distance between genomes

The syntenic distance between two genomes is given by the minimum number of fusions, fissions, and translocations required to transform one into the other, ignoring the order of genes within chromosomes. Computing this distance is NP-hard. In the present work, we give a tight connection between syntenic distance and the incomplete gossip problem, a novel generalization of the classical gossip problem. In this problem, there are n gossipers, each with a unique piece of initial information; they communicate by phone calls in which the two participants exchange all their information. The goal is to minimize the total number of phone calls necessary to inform each gossiper of his set of relevant gossip which he desires to learn. As an application of the connection between syntenic distance and incomplete gossip, we derive an O(2^O(nlogn)) algorithm to exactly compute the syntenic distance between two genomes with at most n chromosomes each. Our algorithm requires O(n²+2^O(dlogd)) time when this distance is d, improving the O(n²+2^O(d2)) running time of the best previous exact algorithm.     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs

We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n²logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n²logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions.     

Fast broadcasting and gossiping in radio networks

We establish an O(nlog²n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n^3/2). Using our broadcasting algorithm, we develop an O(n^3/2log²n) algorithm for gossiping in the same network model.     

Efficient parallel exponentiation in using normal basis representations

Von zur Gathen proposed an efficient parallel exponentiation algorithm in finite fields using normal basis representations. In this paper we present a processor-efficient parallel exponentiation algorithm in GF(qⁿ) which improves upon von zur Gathen's algorithm. We also show that exponentiation in GF(qⁿ) can be done in O((log₂n)²/log_qn) time using n/(log₂n)² processors. Hence we get a processor-time bound of O(n/log_qn), which matches the best known sequential algorithm. Finally, we present an efficient on-line processor assignment scheme which was missing in von zur Gathen's algorithm.     

A faster polynomial algorithm for the unbalanced Hitchcock transportation problem

We present a new algorithm for the Hitchcock transportation problem. On instances with n sources and k sinks, our algorithm has a worst-case running time of O(nk²(logn+klogk)). It closes a gap between algorithms with running time linear in n but exponential in k and a polynomial-time algorithm with running time O(nk²log²n).     

Efficient Algorithms for Finding a Core of a Tree with a Specified Length

Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑_v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log²n) time usingO(n) processors on an EREW PRAM model.     

On the performance of peeling algorithms

The peeling of a d-dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst-case convex hull algorithm, known to have an O(n^˙ Log (n)) execution time, may give an O(n^˙n^˙ Log (n)) to peel all the set; an O(n^˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n-n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n^˙n) performance.     

Ramsey-type results for oriented trees

For a graph G and a digraph (RIGHT ARROW ABOVE H), we write G → (RIGHT ARROW ABOVE H) (respectively, G (A ABOVE RIGHT ARROW)(RIGHT ARROW ABOVE H) if every orientation (respectively, acyclic orientation) of the edges of G results in an induced copy of (RIGHT ARROW ABOVE H). In this note we study how small the graphs G such that G → (RIGHT ARROW ABOVE H) or such that G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE H) may be, if (RIGHT ARROW ABOVE H) is a given oriented tree (RIGHT ARROW ABOVE T)ⁿ on n vertices. We show that there is a graph on O(n⁴ log n) vertices and O(n⁶(log n)²) edges such that G → Tⁿ for every n-vertex oriented tree (RIGHT ARROW ABOVE T)ⁿ. We also prove that there exists a graph G with O(n² log n) vertices and O(n³(log n)²) edges such that G → (RIGHT ARROW ABOVE T)ⁿ for any such tree (RIGHT ARROW ABOVE T)ⁿ. This last result turns out to be nearly best possible as it is shown that any graph G with G (A ABOVE RIGHT ARROW) (RIGHT ARROW ABOVE P)ⁿ, where (RIGHT ARROW ABOVE P)ⁿ is the directed path of order n, has more than n²/2 vertices and more than [n/3]³ edges if n ≥ 3. © 1996, John Wiley & Sons, Inc.     

Efficient reduction for path problems on circular-arc graphs

An efficient reduction process for path problems on circular-arc graphs is introduced. For the parity path problem, this reduction gives anO(n+m) algorithm for proper circular-arc graphs, and anO(n+m) algorithm for general circular-arc graphs. This reduction also gives anO(n+m) algorithm for the two path problem on circular-arc graphs.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

Fast Algorithm for Cross-Validation of the Best Linear Unbiased Predictor

This article proposes a new algorithm for cross-validation of the best linear unbiased predictor. The algorithm relies on a new technique for downdating the inverse of a Cholesky factor. Given n data points, the new algorithm has complexity O(n³), compared to O(n⁴), which is the order for the more traditional delete one and recalculate method.     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Computing homotopic shortest paths in the plane

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160–169; Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. Algorithms, 2002, pp. 411–423]. The algorithm for non-simple paths achieves O(log²n) time per output vertex which is an improvement by a factor of O(n/log²n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63–98], where n is the number of obstacles. The running time has an overhead O(n²⁺) for any positive constant . In the case k<n²⁺, where k is the total size of the input and output, we improve the running to O((n+k+(nk)^2/3)log^O(1)n).     

Planar rectilinear shortest path computation using corridors

The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L₁-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3/2), which is close to the known lower bound of Ω(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together.     

Rectilinear shortest paths in the presence of rectangular barriers

In this paper we address the following shortest-path problem. Given a point in the plane andn disjoint isothetic rectangles (barriers), we want to construct a shortestL ₁ path (not crossing any of the barriers) from the source point to any given query point. A restricted version of this problem (where the source and destination points are knowna priori) had been solved earlier inO(n ²) time. Our approach consists of preprocessing the source point and the barriers to obtain a planar subdivision where a query point can be located and a shortest path connecting it to the source point quickly transvered. By showing that any such path is monotone in at least one ofx ory directions, we are able to apply a plane sweep technique to divide the plane intoO(n) rectangular regions. This leads to an algorithm whose complexity isO(n logn) preprocessing time,O(n) space, andO(logn+k) query time, wherek is the number of turns on the reported path. If only the length of the path is sought,O(logn) query time suffices. Furthermore, we show an (n logn) time lower bound for the case where the source and destination points are known in advance, which implies the optimality of our algorithm in this case.A preliminary version of this paper appeared in theProceedings of the First Symposium on Computational Geometry (1985).Supported in part by CNPq-Conselho Nacional de Desenvolvimento Científico e Tecnológico (Brazil).Supported in part by the National Science Foundation under Grants MCS 8420814 and ECS 8340031.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.