The minimum rectilinear Steiner tree (RST) problem is one of the fundamental problems in the field of electronic design automation. The problem is NP-hard, and much work has been devoted to designing good heuristics and approximation algorithms; to date, the champion in solution quality among RST heuristics is the Batched Iterated 1-Steiner (BI1S) heuristic of Kahng and Robins. In a recent development, exact RST algorithms have witnessed spectacular progress: The new release of the GeoSteiner code of Warme et al. has average running time comparable to that of the fastest available BI1S implementation, due to Robins. We are, thus, faced with the paradoxical situation that an exact algorithm for an NP-hard problem is competitive in speed with a state of-the-art heuristic for the problem. The main contribution of this paper is a new RST heuristic, which has at its core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani for the metric Steiner tree problem on quasi-bipartite graphs-these are graphs that do not contain edges connecting pairs of Steiner vertices. The RV algorithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation. Our heuristic achieves a good running time by combining an efficient implementation of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real very large scale integrated instances show that the new RST heuristic runs significantly faster than Robins' implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than BI1S.

The minimum rectilinear Steiner tree (RST) problem is one of the fundamental problems in the field of electronic design automation. The problem is NP-hard, and much work has been devoted to designing good heuristics and approximation algorithms; to date, the champion in solution quality among RST heuristics is the Batched Iterated 1-Steiner (BI1S) heuristic of Kahng and Robins (1992). In a recent development, exact RST algorithms have witnessed spectacular progress: the new release of the GeoSteiner code of Warme, Winter, and Zachariasen (1998) has average running time comparable to that of the fastest available Bl1S implementation, due to Robins. We are thus faced with the paradoxical situation that an exact algorithm for an NP-hard problem is competitive in speed with a state-of-the-art heuristic for the problem. The main contribution of this paper is a new RST heuristic, which has at its core a recent 3/2 approximation algorithm of Rajagopalan and Vazirani (1999) for the metric Steiner tree problem on quasi-bipartite graphs-these are graphs that do not contain edges connecting pairs of Steiner vertices. The RV algorithm is built around the linear programming relaxation of a sophisticated integer program formulation, called the bidirected cut relaxation. Our heuristic achieves a good running time by combining an efficient implementation of the RV algorithm with simple, but powerful geometric reductions. Experiments conducted on both random and real VLSI instances show that the new RST heuristic runs significantly faster than Robins' implementation of BI1S and than the GeoSteiner code. Moreover, the new heuristic typically gives higher-quality solutions than Bl1S.

the iterative algorithm, which simply relaxes the constraint it is currently considering at the time the overconstraint is detected. Once a valid 2-coloring has been computed, it is simple to trans- late the colors of each trio of vertices back into an orientation for the corresponding device, using the translations given in Table 1. When this is done, each device will have been assigned an orien- tation such that all constraints that were not relaxed due to over- constraints are satisfied. Each coloring attempt requires O(n + m) time [2], where n is the number of devices and m is the number of constraints (which is within a constant multiple of the number of edges in the graphs). This process, as well as the procedure that decides which constraint in an overconstraint to relax, is repeated once each time an overconstraint is found. Thus, if there are c overconstraints and m) is the time required by the overconstraint re

This paper provides a very simple two-approximation algorithm for two NP-hard problems that arise in electronic circuit design. To our knowledge, this is the best approximation bound known for these problems. In addition, the simplicity of the proposed algorithm makes it attractive for real-time applications for similar problems in areas such as telecommunications and parallel processing.

The minimum-congestion hypergraph embedding in a cycle (MCHEC) problem is to embed the n edges in an m-vertex hypergraph as paths in a cycle on the same number of vertices, such that congestion-the maximum number of paths that use any single edge in the cycle-is minimized. The MCHEC problem has applications in electronic design automation and parallel computing. In this paper, it is proven that the MCHEC problem is NP-complete. An O((nm)/sup k+1/) algorithm is described that computes an embedding with congestion k or determines that such an embedding does not exist. Finally, a linear-time approximation algorithm for arbitrary instances is presented that computes an embedding whose congestion is at most three times optimal.

Moat routing is the routing of nets between the input/output pads and the core circuit. In this paper, it is proved that moat routing is NP-complete under the routing model in which there are no vertical conflicts and doglegs are disallowed (i.e., every net is routed within a single track). This contrasts with the fact that channel routing is efficiently solvable under these restrictions. The paper then presents an approximation algorithm for moat routing that computes moat routing solutions that are guaranteed to use at most four times the optimal number of tracks. Empirical results are presented indicating that for a number of industrial benchmarks, the algorithm produces solutions that are near optimal and that use significantly fewer tracks than previous moat routing strategies.

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a fully-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing the performance of this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms, based on geometric partitioning, global routing of field-programmable gate arrays, and routing estimation during floorplanning.

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a full-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms based on geometric partitioning and in global routing of field-programmable gate arrays.

An exact rectilinear Steiner minimal tree algorithm is presented that improves upon the time and space complexity of previous guarantees and is easy to implement. Experimental evidence is presented that demonstrates that the algorithm also works well in practice.>

This paper presents a new model for VLSI routing in the presence of obstacles, that transforms any routing instance from a geometric problem into a graph problem. It is the first model that allows computation of optimal obstacle-avoiding rectilinear Steiner trees in time corresponding to the instance size (the number of terminals and obstacle border segments) rather than the size of the routing area. For the most common multi-terminal critical nets-those with three or four terminals-we observe that optimal trees can be computed as efficiently as good heuristic trees, and present algorithms that do so. For nets with five or more terminals, we present algorithms that heuristically compute obstacle-avoiding Steiner trees. Analysis and experiments demonstrate that the model and algorithms work well in both theory and practice.>

The behavior of random graphs with respect to graph partitioning is considered. It is shown that, for a random graph with n vertices and with expected degree exceeding a constant times ln n, the graph cannot be partitioned well, i.e. a random partition is likely to be almost as good as an optimal partition.