The ordered binary decision diagram is a canonical representation for Boolean functions, presented by R.E. Bryant (1985) as a compact representation for a broad class of interesting functions derived from circuits. However, the size of the diagram is very sensitive to the choice of ordering on the variables; hence, for some applications, such as differential cascode voltage switch (DCVS) trees, it becomes extremely important to find the ordering leading to the most compact representation. An algorithm for this problem with time complexity O(n/sup 2/3/sup n/) is presented. This represents an improvement over the previous best algorithm.>

The main result of this paper is an 0 ([ V ] x [ E ]) time algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. The algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices. Furthermore, as a substep of the algorithm, it is shown how to find in 0 ([ V ] x [ E ]) time a decomposition of a graph into prime graphs, thereby improving on a result of Cunningham.

The ordered binary decision diagram is a canonical representation for Boolean functions, presented by Bryant as a compact representation for a broad class of interesting functions derived from circuits. However, the size of the diagram is very sensitive to the choice of ordering on the variables; hence for some applications, such as Differential Cascode Voltage Switch (DCVS) trees, it becomes extremely important to find the ordering leading to the most compact representation. We present an algorithm for this problem with time complexity O(n/sup 2/3/sup n/), an improvement over the previous best, which required O(n!2/sup n/).

Let S be any set of N points in the plane and let DT(S) be the graph of the Delaunay triangulation of S. For all points a and b of S, let d(a, b) be the Euclidean distance from a to b and let DT(a, b) be the length of the shortest path in DT(S) from a to b. We show that there is a constant c(≤ 1+√5/2 π ≈ 5.08) independent of S and N such that DT(a, b)/d(a, b) ≪ c.

Abstract The Sethi‐Ullman algorithm for register allocation finds an optimal ordering of a computation tree. Two simple generalizations of the algorithm increase its applicability without significantly increasing its cost.

An algorithm is presented that, given N two-pin nets in a channel, finds, in O(N/sup 2/) time, the largest subset that can be routed all on one layer

We present an algorithm for deciding whether two given synchronous, logic-level sequential circuits are functionally equivalent. Our approach involves a formal symbolic comparison, as opposed to the (often very time-consuming) generation and simulation of numerous test vector sequences. The given circuits need not have the same number of states, nor must they have the same number of inputs — for example, one circuit may be a parallel implementation and the other serial. Although this is an intractable problem in general, we believe that the method is useful on a broad class of practical circuits; our computational experience thus far is encouraging.

The customary need for rejection of candidate moves in simulated annealing is eliminated by biasing the selection of moves according to their effect on the cost function. An efficient implementation can offer a significant speed-up, though with increased memory. The logic partitioning problem is used as an illustration; both simple moves and pairwise interchanges are considered.

Our main result is a polynomialtime algorithm for deciding whether a given graph is a circle graph, that is, the intersection graph of a set of chords on a circle. Our algorithm utilizes two new graph-theoretic results, regarding necessary induced subgraphs of graphs having neither articulation points nor similar pairs of vertices.

Given n demand points in the plane, the p-center problem is to find p supply points (anywhere in the plane) so as to minimize the maximum distance from a demand point to its respective nearest supply point. The p-median problem is to minimize the sum of distances from demand points to their respective nearest supply points. We prove that the p-center and the p-median problems relative to both the Euclidean and the rectilinear metrics are NP-hard. In fact, we prove that it is NP-hard even to approximate the p-center problems sufficiently closely. The reductions are from 3-satisfiability.

A new methodology for the automatic layout of integrated circuits is presented. The methodology, based on a hierarchical description of the circuit, is a hybrid between standard cell and fully custom, having the advantages of both. It has the ease of placement and routing of standard cell, combined with the ability to handle large numbers of diverse cells as in fully custom. The methodology has been implemented and applied to several circuits, with very encouraging results.

The relative neighborhood graph (RNG) of a set V of pomts in Euchdean space is the graph (V, E), where (p, q) E E iff there is no point z E V such that d(p, z) < d(p, q) and d(q, z) < d(p, q) It is shown that (1) the RNG of n points in the' plane can be found in O(n log n) time, which is optimal to wRlun a multiphcative constant.(2) The RNG, as well as the minimum spanning tree, of the vertices of a convex, n-vertex polygon can be found m O(n) time, given the vertices m sorted clockwise order.(3) Under the assumption that no three input points form an isosceles triangle, the RNG of n points m rdimensional space can be found m O(n 2) time for fixed r >_ 3.Categories and SubJect Descriptors: F

Abstract The expected costs of the matchings found by various divide‐and‐conquer heuristic algorithms are calculated, under the assumption that the vertices to be matched are uniformly distributed in the unit square. The expected times of the algorithms are calculated as well.

We consider the following problem: Given n points in a unit square in the Euclidean plane, find a matching of the points such that the cost (i.e., the sum of the lengths of the edges between matched points) is minimum. In particular, we present a class of linear time heuristic algorithms for this problem and analyze their worst case performance. The worst case performance of an algorithm is defined as the greatest possible cost, as a function of n, of the matching produced by the algorithm on a set of n points. Each of the algorithms studied here divides the unit square into a few smaller regions, and then is applied recursively to the points in each of these regions.

We show that the cost (length) of the shortest traveling salesman tour through n points in the unit square is, in the worst case, $\alpha _{{\text{opt}}}^{{\text{tsp}}} \sqrt n + o(\sqrt n )$, where $1.075 \leqq \alpha _{{\text{opt}}}^{{\text{tsp}}}\leqq 1.414$. The cost of the minimum matching of n points in the unit square is shown to be, in the worst case, $\alpha _{{\text{opt}}}^{{\text{mat}}} \sqrt n + o(\sqrt n )$, where $0.537 \leqq \alpha _{{\text{opt}}}^{{\text{mat}}} \leqq 0.707$. Furthermore, for each of these two problems there is an almost linear time heuristic algorithm whose Worst case cost is, neglecting lower order terms, as low as b Bible.

The inherent computational complexity of polygon decomposition problems is of theoretical interest to researchers in the field of computational geometry and of practical interest to those working in syntactic pattern recognition. Three polygon decomposition problems are shown to be NP-hard and thus unlikely to admit efficient algorithms. The problems are to find minimum decompositions of a polygonal region into (perhaps overlapping) convex, star-shaped, or spiral subsets. We permit the polygonal region to contain holes. The proofs are by transformation from Boolean three-satisfiability, a known NP-complete problem. Several open problems are discussed.

A routing heuristic is presented thatroutes two-terminal nets one at a time, for each net choosing the path so as to avoid adversely impacting the nets not yet routed. An algorithm is presented and proved to correctly implement this heuristic; the computational complexity of that algorithm is shown to be polynomially bounded, but perhaps still too great to be of practical use. Another, speedier algorithm is presented that seems to approximate the heuristic rather closely. Strong evidence is given that the Lee routing algorithm is in some sense inadequate to implement this heuristic.

The problem of finding near optimal perfect matchings of an even number n of vertices is considered. When the distances between the vertices satisfy the triangle inequality it is possible to get within a constant multiplicative factor of the optimal matching in time O(n2 log K) where K is the ratio of the longest to the shortest distance between vertices. Other heuristics are analyzed as well, including one that gets within a logarithmic factor of the optimal matching in time O(n2 log n). Finding an optimal weighted matching requires t(n3) time by the fastest known algorithm, so these heuristics are quite useful. When the n vertices lie in the unit (Euclidean) square, no heuristic can be guaranteed to produce a matching of cost less than [equation] in the worst case. We analyze various heuristics for this case, including one that always produces a matching costing at most [equation]. In addition, this heuristic also finds a traveling salesman tour of the n vertices costing at most [equation]. A different one of the heuristics analyzed produces asymptotically optimal results. It is also shown that asymptotically optimal traveling salesman tours can be found in O(n log n) time in the unit square.