On approximating the longest path in a graph

We consider the problem of approximating the longest path in undirected graphs. In an attempt to pin down the best achievable performance ratio of an approximation algorithm for this problem, we present both positive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of finding paths in graphs that are guaranteed to have extremely long paths. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of graphs (weakly Hamiltonian), where the result is the best possible. Since the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broderet al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any ε<1, the problem of finding a path of lengthn-n ^ε in ann-vertex Hamiltonian graph isNP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unlessP=NP. We conjecture that the result can be strengthened to say that, for some constant δ>0, finding an approximation of ration ^δ is alsoNP-hard. As evidence toward this conjecture, we show that if any polynomial-time algorithm can approximate the longest path to a ratio of , for any ε>0, thenNP has a quasi-polynomial deterministic time simulation. The hardness results apply even to the special case where the input consists of bounded degree graphs. D. Karger was supported by an NSF Graduate Fellowship, NSF Grant CCR-9010517, and grants from the Mitsubishi Corporation and OTL. R. Motwani was supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award, grants from Mitsubishi and OTL, NSF Grant CCR-9010517, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, the Schlumberger Foundation, the Shell Foundation, and the Xerox Corporation, G. D. S. Ramkumar was supported by a grant from the Toshiba Corporation. Communicated by M. X. Goemans.     

Merging video streams in a multimedia storage server: complexity and heuristics

Due to recent advances in network, storage and data compression technologies, video-on-demand (VOD) service has become economically feasible. It is a challenging task to design a video storage server that can efficiently service a large number of concurrent requests on demand. One approach to accomplishing this task is to reduce the I/O demand to the VOD server through data- and resource-sharing techniques. One form of data sharing is the stream-merging approach proposed in [5]. In this paper, we formalize a static version of the stream-merging problem, derive an upper bound on the I/O demand of static stream merging, and propose efficient heuristic algorithms for both static and dynamic versions of the stream-merging problem.     

Parallel watershed transformation algorithms for image segmentation

The watershed transformation is a mid-level operation used in morphological image segmentation. Techniques applied on large images, which must often complete fast, are usually computationally expensive and complex entailing efficient parallel algorithms. Two distributed approaches of the watershed transformation are introduced in this paper. The algorithms survey in a Single Program Multiple Data (SPMD) model both local and global connectivity properties of the morphological gradient of a gray-scale image to label connected components. The sequentiality of the serial algorithm is broken in the parallel versions by exploiting the ordering relation between two neighboring pixels successively incorporated in the same region. Thus, a path is traced, for every unlabeled pixel, down to its region of inclusion (whose label is then propagated backwards); in the second algorithm, regions grow independently around their seeds. In both cases only pixels which satisfy the ordering relation are incorporated in any region. This way, not only different regions are explored in a parallel fashion, but also different parts of the same region, when the latter extends to neighboring subdomains, are treated likewise. Running time and relative speedup evaluated on a Cray T3D parallel computer are used to appreciate the performance of both algorithms.     

A simple linear algorithm for intersecting convex polygons

LetP andQ be two convex polygons withm andn vertices, respectively, which are specified by their cartesian coordinates in order. A simpleO(m+n) algorithm is presented for computing the intersection ofP andQ. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.     

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).     

HVMDM:一个实用的软件系统级设计模型

依据ＨＶＭ（Ｈｏｒｉｚｏｎｔａｌ－Ｖｅｒｔｉｃａｌ Ｍｅｔａｄａｔａ）方法,给出了一个软件系统级设计模型ＨＶＭＤＭ（ＨＶＭ Ｄｅｓｉｇｎ Ｍｏｄｅｌ）,并把这一模型应用到大型ＭＩＳ系统的设计中。分析了在系统中增加新的子系统时,系统复杂性的增加情况,并与垂直接口方法进行了比较,证明了该方法的有效性。     

A linear algorithm to find a rectangular dual of a planar triangulated graph

We develop anO(n) algorithm to construct a rectangular dual of ann-vertex planar triangulated graph.This research was supported in part by the National Science Foundation under Grant MCS-83-05567.     

Sorting in constant number of row and column phases on a mesh

An algorithm for sorting on a mesh by alternately transforming the rows and columns is presented. The algorithm runs in a constant number of row- and column-transformation phases (sixteen phases), an improvement over the previous best upper bound ofO(log logm) phases,m being the number of rows in the mesh. A corresponding lower bound of five phases is also shown.This research was supported by the National Science Foundation under Grant DCR-84-51396, and by IBM Corporation under Grant D8400622.     

IHDL语言与测试生成系统

本文详细地介绍了一种集成式硬件描述语言（ＩＨＤＬ）和与ＩＨＤＬ相适配的门级电路测试生成系统，实现了从硬件描述语言编译器到自动测试生成的完整系统。从我们的理论分析和实验结果来看，这种完整的系统作为ＥＤＡＣＡＤ中的重要环节是可行的，也是有效的。     

A multilevel parallel solver for block tridiagonal and banded linear systems

This paper describes an efficient algorithm for the parallel solution of systems of linear equations with a block tridiagonal coefficient matrix. The algorithm comprises a multilevel LU-factorization based on block cyclic reduction and a corresponding solution algorithm.

The paper includes a general presentation of the parallel multilevel LU-factorization and solution algorithms, but the main emphasis is on implementation principles for a message passing computer with hypercube topology. Problem partitioning, processor allocation and communication requirement are discussed for the general block tridiagonal algorithm.

Band matrices can be cast into block tridiagonal form, and this special but important problem is dealt with in detail. It is demonstrated how the efficiency of the general block tridiagonal multilevel algorithm can be improved by introducing the equivalent of two-way Gaussian elimination for the first and the last partitioning and by carefully balancing the load of the processors. The presentation of the multilevel band solver is accompanied by detailed complexity analyses.

The properties of the parallel band solver were evaluated by implementing the algorithm on an Intel iPSC hypercube parallel computer and solving a larger number of banded linear equations using 2 to 32 processors. The results of the evaluation include speed-up over a sequential processor, and the measure values are in good agreement with the theoretical values resulting from complexity analysis. It is found that the maximum asymptotic speed-up of the multilevel LU-factorization using p processors and load balancing is approximated well by the expression (p +6)/4.

Finally, the multilevel parallel solver is compared with solvers based on row and column interleaved organization.