An efficient all-parses systolic algorithm for general context-free parsing

The problem of outputting all parse trees of a string accepted by a context-free grammar is considered. A systolic algorithms is presented that operates inO(m·n) time, wherem is the number of distinct parse trees andn is the length of the input. The systolic array usesn ² processors, each of which requires at mostO(logn) bits of storage. This is much more space-efficient that a previously reported systolic algorithm for the same problem, which requiredO(n logn) space per processor. The algorithm also extends previous algorithms that only output a single parse tree of the input.Research squpported in part by NSF Grant DCR-8420935 and DCR-8604603.     

Exact Algorithms for MAX-SAT

The maximum satisfiability problem (MAX-SAT) is stated as follows: Given a boolean formula in CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-SAT is MAX-SNP-complete and received much attention recently. One of the challenges posed by Alber, Gramm and Niedermeier in a recent survey paper asks: Can MAX-SAT be solved in less than 2ⁿ “steps”? Here, n is the number of distinct variables in the formula and a step may take polynomial time of the input. We answered this challenge positively by showing that a popular algorithm based on branch-and-bound is bounded by O(2ⁿ) in time, where n is the maximum number of occurrences of any variable in the input.When the input formula is in 2-CNF, that is, each clause has at most two literals, MAX-SAT becomes MAX-2-SAT and the decision version of MAX-2-SAT is still NP-complete. The best bound of the known algorithms for MAX-2-SAT is O(m2^m/5), where m is the number of clauses. We propose an efficient decision algorithm for MAX-2-SAT whose time complexity is bound by O(n2ⁿ). This result is substantially better than the previously known results. Experimental results also show that our algorithm outperforms any algorithm we know on MAX-2-SAT.     

k best cuts for circular-arc graphs

Given a set ofn nonnegativeweighted circular arcs on a unit circle, and an integerk, thek Best Cust for Circular-Arcs problem, abbreviated as thek-BCCA problem, is to find a placement ofk points, calledcuts, on the circle such that the total weight of the arcs that contain at least one cut is maximized. We first solve a simpler version, thek Best Cuts for Intervals (k-BCI) problem, inO(kn+n logn) time andO(kn) space using dynamic programming. The algorithm is then extended to solve a variation, called thek-restricted BCI problem, and the space complexity of thek-BCI problem can be improved toO(n). Based on these results, we then show that thek-BCCA problem can be solved inO(I(k,n)+nlogn) time, whereI(k, n) is the time complexity of thek-BCI problem. As a by-product, thek Maximum Cliques Cover problem (k>1) for the circular-arc graphs can be solved inO(I(k,n)+nlogn) time. This work was supported in part by the National Science Foundation under Grants CCR-8901815, CCR-9309743, and INT-9207212, and by the Office of Naval Research under Grant No. N00014-93-1-0272.     

Fast 3-coloring Triangle-Free Planar Graphs

Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n ²) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is O(nlogn)\mathcal{O}(n\log n) .     

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.     

Computing the Greedy Spanner in Near-Quadratic Time

The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n²logn)\ensuremath {\mathcal {O}}(n^{2}\log n) time. Since computing the greedy spanner has an Ω(n ²) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.     

Finding least-weight subsequences with fewer processors

By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takesO(log² n) time on a CREW PRAM with n³/logn processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log² n log logn) time withn/log logn processors, or in O(log² n) time withn logn processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12].     

An O ( n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks

   Abstract. We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D , we present an adaptive deterministic gossiping algorithm of time O (

Selecting distances in the plane

We present a randomized algorithm for computing the kth smallest distance in a set ofn points in the plane, based on the parametric search technique of Megiddo [Mel]. The expected running time of our algorithm is O(n^4/3 log^8/3 n). The algorithm can also be made deterministic, using a more complicated technique, with only a slight increase in its running time. A much simpler deterministic version of our procedure runs in time O(n^3/2 log^5/2 n). All versions improve the previously best-known upper bound ofO(@#@ n^9/5 log^4/5 n) by Chazelle [Ch]. A simpleO(n logn)-time algorithm for computing an approximation of the median distance is also presented.Part of this work was done while the first two authors were visting DIMACS, Rutgers University, New Brunswick, NJ. Work by the first three authors has been partly supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center-NSF-STC88-09648. Work by the second author has also been supported by National Security Agency Grant MDA 904-89-H-2030. Work by the third author has also been supported by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Time-Space Tradeoff in Derandomizing Probabilistic Logspace

Nisan showed that any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated by a deterministic algorithm that runs simultaneously in polynomial time and Θ(log² n) space. Subsequently Saks and Zhou improved the space complexity and showed that a deterministic simulation can be carried out in space Θ(log^1.5n). However, their simulation runs in time n^{Θ(log^{0.5}n)}. We prove a time--space tradeoff that interpolates these two simulations. Specifically, we prove that, for any 0 ≤ α ≤ 0.5, any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated deterministically in time n^{O(log^{0.5-α}n)} and space O(log^{1.5+α}n). That is, we prove that BPL ⊆ DTISP[n^{O(log^{0.5-α}n)}, O(log^1.5+αn)].     

Sorting-Based Selection Algorithms for Hypercubic Networks

This paper presents several deterministic algorithms for selecting the k th largest record from a set of n records on any n -node hypercubic network. All of the algorithms are based on the selection algorithm of Cole and Yap, as well as on various sorting algorithms for hypercubic networks. Our fastest algorithm runs in O( lg n lg ^* n) time, very nearly matching the trivial lower bound. Previously, the best upper bound known for selection was O( lg n lg lg n) . A key subroutine in our O( lg n lg ^* n) time selection algorithm is a sparse version of the Sharesort algorithm that sorts n records using p processors, , in O( lg n ( lg lg p - lg lg (p/n) ) ² ) time. Received March 23, 1994; revised October 30, 1997.     

Improved edge-coloring with three colors

We show an O(1.344ⁿ)=O(2^0.427n) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous O(2^n/2) algorithm of Beigel and Eppstein [R. Beigel, D. Eppstein, 3-coloring in time O(1.3289n), J. Algorithms 54 (2) (2005) 168–204.]. We apply a very natural approach of generating inclusion–maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.     

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.     

Computing shortest transversals

We present anO(nlog² n) time andO(n) space algorithm for computing the shortest line segment that intersects a set ofn given line segments or lines in the plane. If the line segments do not intersect the algorithm may be trimmed to run inO(nlogn) time. Furthermore, in combination with linear programming the algorithm will also find the shortest line segment that intersects a set ofn isothetic rectangles in the plane inO(nlogk) time, wherek is the combinatorial complexity of the space of transversals andk≤4n. These results find application in: (1) line-fitting between a set ofn data ranges where it is desired to obtain the shortestline-of-fit, (2) finding the shortest line segment from which a convexn-vertex polygon is weakly externally visible, and (3) determing the shortestline-of-sight between two edges of a simplen-vertex polygon, for whichO(n) time algorithms are also given. All the algorithms are based on the solution to a new fundamental geometric optimization problem that is of independent interest and should find application in different contexts as well.     

Fast stable in-place sorting withO(n) data moves

Until recently, it was not known whether it was possible to sortstably (i.e., keeping equal elements in their initial order) an array ofn elements using onlyO(n) data moves andO(1) extra space. In [13] an algorithm was given to perform this task inO(n ²) comparisons in the worst case. Here, we develop a new algorithm for the problem that performs onlyO(n ¹⁺) comparisons (0<<1 is any fixed constant) in the worst case. This bound on the number of comparisons matches (asymptotically) the best known bound for the same problem with the stability constraint dropped.A version of this paper appeared in theProceedings-of the 11th FST & TCS Conference [9]. This research was supported by NSERC of Canada grant No. A-8237 and the ITRC of Ontario.     

Exact and approximation algorithms for sorting by reversals,with application to genome rearrangement

Motivated by the problem in computational biology of reconstructing the series of chromosome inversions by which one organism evolved from another, we consider the problem of computing the shortest series of reversals that transform one permutation to another. The permutations describe the order of genes on corresponding chromosomes, and areversal takes an arbitrary substring of elements, and reverses their order.For this problem, we develop two algorithms: a greedy approximation algorithm, that finds a solution provably close to optimal inO(n ²) time and0(n) space forn-element permutations, and a branch- and-bound exact algorithm, that finds an optimal solution in0(mL(n, n)) time and0(n ²) space, wherem is the size of the branch- and-bound search tree, andL(n, n) is the time to solve a linear program ofn variables andn constraints. The greedy algorithm is the first to come within a constant factor of the optimum; it guarantees a solution that uses no more than twice the minimum number of reversals. The lower and upper bounds of the branch- and-bound algorithm are a novel application of maximum-weight matchings, shortest paths, and linear programming.In a series of experiments, we study the performance of an implementation on random permutations, and permutations generated by random reversals. For permutations differing byk random reversals, we find that the average upper bound on reversal distance estimatesk to within one reversal fork<1/2n andn<100. For the difficult case of random permutations, we find that the average difference between the upper and lower bounds is less than three reversals forn<50. Due to the tightness of these bounds, we can solve, to optimality, problems on 30 elements in a few minutes of computer time. This approaches the scale of mitochondrial genomes.This research was supported by a postdoctoral fellowship from the Program in Mathematics and Molecular Biology of the University of California at Berkeley under National Science Foundation Grant DMS-8720208, and by a fellowship from the Centre de recherches mathématiques of the Université de Montréal.This research was supported by grants from the Natural Sciences and Engineering Research Council of Canada, and the Fonds pour la formation de chercheurs et l'aide à la recherche (Québec). The author is a fellow of the Canadian Institute for Advanced Research.     

A linear algorithm for eliminating hidden-lines from a polygonal cylinder

A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity ofO(n ²). It is the interent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications.     

On constructing the relative neighborhood graphs in EuclideanK-dimensional spaces

In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of ann points set in Euclideank-dimensional space is presented, for fixedk≥3. The worst case running time of the algorithm isO(n ^2?a(k) (logn)^1?a(k) ), fora(k)=2^?(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms needO(n ²) time. Our algorithm proceeds in two phases. First, a supergraph ofRNG withO(n) edges is constructed and then those edges which do not belong toRNG are eliminated.     

Visibility problems for orthogonal objects in two-or three-dimensions

LetP be a set ofl points in 3-space, and letF be a set ofm opaque rectangular faces in 3-space with sides parallel tox- ory-axis. We present anO(n logn) time andO(n) space algorithm for determining all points inP which are visible from a viewpoint at (0,0,), wheren=l+m. We also present anO(n logn+k) time andO(n) space algorithm for the hidden-line elimination problem for the orthogonal polyhedra together with a viewpoint at (0,0,), wheren is the number of vertices of the polyhedra andk is the number of edge intersections in the projection plane.