The integers: = {...,-3,-2,-1,0,1,2,3,...} (2009)
A set is formally an undefined term, but intuitively it is a (possibly empty) collection of arbitrary objects. A set is usually denoted by curly braces and some (optional) restrictions. Examples of...
Moving-Target TSP and Related Problems \Lambda (2008)
C. S. Helvig, Gabriel Robins, Alex Zelikovsky
Abstract Previous literature on the Traveling Salesman Problem (TSP) assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent...
New Performance�Driven FPGA Routing Algorithms � (2008)
Michael J. Alex, Gabriel Robins
Motivated by the goal of increasing the performance of FPGA�based designs � we propose e�ective Steiner and arborescence FPGA routing algorithms. Our graph� based Steiner tree constructions...
Abstract Evaluation of the New OASIS Format for Layout Fill Compression ∗ (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
SIS) has been recently proposed for replacing the GDSII format. A primary objective of the new OASIS format is to enhance the compressibility of layout data. We compare the data compression...
Yu Chen, Andrew B. Kahng, Gabriel Robins
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difcult with the introduction of new materials such as copper and low-k...
New Approximation Algorithms for Routing with Multiport Terminals (2008)
Christopher S. Helvig, Gabriel Robins, Er Zelikovsky
Abstract-Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each...
New Performance-Driven FPGA Routing Algorithms (2008)
Michael J. Alex, Gabriel Robins
Abstract—Motivated by the goal of increasing the performance of FPGA-based designs, we propose new Steiner and arborescence FPGA routing algorithms. Our Steiner tree constructions significantly...
Abstract Evaluation of the New OASIS Format for Layout Fill Compression ∗ (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
SIS) has been recently proposed for replacing the GDSII format. A primary objective of the new OASIS format is to enhance the compressibility of layout data. We compare the data compression...
High-Performance Routing for Field-Programmable Gate Arrays* (2008)
Michael J. Alex, Gabriel Robins
The advantages of field-programmable gate ar-rays (FPGAs) are sometimes eclipsed by a substan-tial performance penalty due to signal delay through the programmable routing resources. We propose Q new...
Performance-Oriented Placement and Routing for Field-Programmable Gate Arrays * (2008)
Michael J. Alex, James P. Cohoon, Joseph L. Ganleyt, Gabriel Robins
This paper presents a performance-oriented placement and routing tool for field-programmable gate arrays. Using recursive geometric partitioning for simulta-neous placement and global routing, and a...
A Potential-Based Proof for a Certain Pebbling Game and its Generalization (2008)
In this paper we define a type of pebbling game played on an infinite planar rectangular mesh. We are concerned with whether certain configurations are reachable from a particular initial...
Signal Constellation Design Tool: A Case study in User Interface Synthesis (2008)
Signal constellation design is a major subtask of constructing an efficient communication system; it essentially entails trading-off error frequency against information throughput, a chief occupation...
Some common The natural The The The (2008)
"When I use a word, " Humpty Dumpty said, in a rather scornful tone, "it means just what I choose it to mean-- neither more nor less." A set is formally an...
Three-Dimensional Field-Programmable Gate Arrays * (2008)
Michael J. Alex, James P. Cohoon, Jared L. Colflesh, John Karro, Gabriel Robins
Motivated by improving FPGA performance, we propose a new three-dimensional (3U) FPGA archi-tecture, along with a fabrication methodology. We an-alyze the expected manufacturing yield, and raise...
Jeff Griffith, Gabriel Robins, Jeffrey S. Salowe, Tongtong Zhang
Abstract-The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NPhard, and the best...
New Approximation Algorithms for Routing with Multiport Terminals (2008)
Christopher S. Helvig, Gabriel Robins, Er Zelikovsky
Abstract—Previous literature on very large scale integration routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each...
The Moving-Target Traveling Salesman Problem (2008)
C. S. Helvig, Gabriel Robins, Alex Zelikovsky
Previous literature on the Traveling Salesman Problem (TSP) assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent generalization of...
Extraction of human DNA replication timing patterns from discrete microarray data (2008)
Dutta, Anindya, Karnani, Neerja, Malhotra, Ankit, Robins, Gabriel, Taylor, Christopher M.
Effective reproduction is essential for the survival and proliferation of any organism, from the birth of new offspring to the repro- duction of individual cells. Each portion of a cell’s DNA must...
Extraction of human DNA replication timing patterns from discrete microarray data (2008)
Dutta, Anindya, Karnani, Neerja, Malhotra, Ankit, Robins, Gabriel, Taylor, Christopher M.
Effective reproduction is essential for the survival and proliferation of any organism, from the birth of new offspring to the repro- duction of individual cells. Each portion of a cell’s DNA must...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Abstract--- To improve manufacturability and performance predictability, we seek to make a layout uniform with respect to prescribed density criteria, by inserting "fill "...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Abstract--- To improve manufacturability and performance predictability, we seek to make a layout uniform with respect to prescribed density criteria, by inserting "fill "...
Monte-Carlo Algorithms for Layout Density Control (2007)
Yu Chen Andrew, Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics of the...
Is Formally An, Gabriel Robins, More Generally
. The logical symbol # (pronounced "for all") denotes universal quantification. For example, the formula "#x#B x # x 2 +1" reads "for all x a member of the real numbers, x is...
New Approximation Algorithms for Routing with Multi-Port Terminals (2007)
C. S. Helvig, Gabriel Robins, Alexander Zelikovsky, Er Zelikovsky
Previous literature on VLSI routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however, each "terminal" consists of a...
Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time (2007)
Tim Barrera, Tim Barrera, Jeff Griffith, Jeff Griffith, Gabriel Robins, Gabriel Robins, ...
We propose several efficient enhancements to the Iterated 1-Steiner (I1S) heuristic of Kahng and Robins [17] for the minimum rectilinear Steiner tree problem. For typical nets, our methods obtain...
New Graph Arborescence and Steiner Constructions for High-Performance FPGA Routing (2007)
Michael J. Alexander, Gabriel Robins
The flexibility and reusability of field-programmable gate arrays (FPGAs) enable significant speed and cost savings in the VLSI design/validation/simulation cycle. However, this is achieved at a...
Optimal Algorithms for Substrate Testing in Multi-Chip Modules (2007)
Andrew B. Kahng, Gabriel Robins, Elizabeth A. Walkup
Multi-chip module (MCM) packaging techniques present several new technical challenges, notably substrate testing. We formulate MCM substrate testing as a problem of connectivity verification in trees...
1 Area Fill Synthesis for Uniform Layout Density (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract--- Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Closing the Smoothness and Uniformity Gap in Area Fill Synthesis (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Control of variability in the back end of the line, and hence in interconnect performance as well, has become extremely difficult with the introduction of new materials such as copper and low-k...
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical planarization (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on the local layout density. To...
Optimal minimum-surface computations using network flow (2007)
We give a computationally-efficient solution to a discrete version of the "Plateau problem" on minimal surfaces. Our approach is based on a novel transformation using network flows...
Gabriel Robins, Alexander Zelikovsky
The Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic with an...
Sean T. Mcculloch, T. Mcculloch, Gabriel Robins, ...
The process of designing an integrated circuit is complex, and is typically broken into several sub-problems, each solved using heuristics. Historically, heuristics for the routing problem have all...
Dallas E. Wrege, Jorg Liebeherr (advisor, William A. Wulf, Gabriel Robins, Stephen G. Strickland, ...
Future integrated-services networks are expected to support applications with a wide range of service requirements. The most demanding applications require a bounded-delay service that provides...
John E. Karro, E. Karro, John A. Stankovic, Gabriel Robins, ...
Field Programmable Gate Arrays (FPGAs) have become an increasingly useful and important architecture in hardware design. As a flexible alternative to custom integrated chips, FPGA-implemented designs...
The practicality of multi-tag rfid systems (2007)
Leonid Bolotnyy, Scott Krize, Gabriel Robins
Radio Frequency Identification (RFID) is an increasingly popular technology that uses radio signals for object identification. Successful object identification is the primary objective of RFID...
The practicality of multi-tag rfid systems (2007)
Leonid Bolotnyy, Scott Krize, Gabriel Robins
Radio Frequency Identification (RFID) is an increasingly popular technology that uses radio signals for object identification. Successful object identification is the primary objective of RFID...
The practicality of multi-tag rfid systems (2007)
Leonid Bolotnyy, Gabriel Robins, Rfid Technologies, M. Sheng, S. Zeadally, Z. Maamar
Successful object identification is the primary objective of radio frequency identification (RFID) technology. Yet, a recent major study by Wal-Mart has shown that object detection probability can be...
Compressible area fill synthesis (2005)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
Abstract—Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k...
Tighter Bounds for Graph Steiner Tree Approximation (2005)
Gabriel Robins, Alexander Zelikovsky
Abstract. The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-ln 3 time...
Compressible area fill synthesis (2005)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky, Yuhong Zheng
Control of variability and performance in the back end of the VLSI manufacturing line has become extremely difficult with the introduction of new materials such as copper and low-k dielectrics. To...
Tighter Bounds for Graph Steiner Tree Approximation (2005)
Gabriel Robins, Alex Zelikovsky
The classical Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-ln 3 time heuristic...
Area fill synthesis for uniform layout density (2002)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract — Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Area fill synthesis for uniform layout density (2002)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
Abstract — Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics...
Sean T. Mcculloch, Gabriel Robins, Sean T. Mcculloch, John C. Knight, ...
The process of designing an integrated circuit is complex, and is typically broken into several sub-problems, each solved using heuristics. Historically, heuristics for the routing problem have all...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
John E. Karro, John A. Stankovic, E. Karro, Gabriel Robins, ...
Field Programmable Gate Arrays (FPGAs) have become an increasingly useful and impor-tant architecture in hardware design. As a exible alternative to custom integrated chips, FPGA-implemented designs...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Monte-Carlo Algorithms for Layout Density Control (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics of the...
Improved Steiner Tree Approximation in Graphs (2000)
Gabriel Robins, Alexander Zelikovsky
The Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of vertices (terminals). We present a new polynomial-time heuristic with an...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Alexander Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
Practical Iterated Fill Synthesis for CMP Uniformity (2000)
Yu Chen, Andrew B. Kahng, Gabriel Robins, Er Zelikovsky
We propose practical iterated methods for layout density control for CMP uniformity, based on linear programming, Monte-Carlo and greedy algorithms. We experimentally study the tradeoffs between two...
New Multilevel and Hierarchical Algorithms for Layout Density Control (1999)
Andrew Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky
Certain manufacturing steps in very deep submicron VLSI involve chemical-mechanical polishing (CMP) which has varying effects on device and interconnect features, depending on local layout...
Generalized neighbor-joining: more reliable phylogenetic tree reconstruction (1999)
William R. Pearson, Gabriel Robins, Tongtong Zhang
We have developed a phylogenetic tree reconstruction method that detects and reports multiple, topologically distant, low cost solutions. Our method is a generalization of the Neighbor-Joining (NJ)...
New and Exact Filling Algorithms for Layout Density Control (1999)
Andrew Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky
To reduce manufacturing variation due to chemicalmechanical polishing and to improve yield, layout must be made uniform with respect to density criteria. This is achieved by layout postprocessing to...
New Multilevel and Hierarchical Algorithms for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky, Er Zelikovsky
Certain manufacturing steps in very deep submicron VLSI involve chemical-mechanical polishing (CMP) which has varying effects on device and interconnect features, depending on local layout...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features, depending on local characteristics of the...
Low-Degree Minimum Spanning Trees (1999)
Gabriel Robins, Jeffrey S. Salowe
Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the Lp norm, the maximum vertex degree over all MSTs is...
On Detecting Spatial Regularity in Noisy Images (1999)
Gabriel Robins, Brian L. Robinson, Bhupinder S. Sethi
Detecting spatial regularity in images arises in computer vision, scene analysis, military applications, and other areas. In this paper we present an O(n 5 2 ) algorithm that reports all maximal...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Er Zelikovsky
Abstract-In very deep-submicron very large scale integration (VLSI), manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features,...
On detecting spatial regularity in noisy images (1999)
Gabriel Robins, Brian L. Robinson, Bhupinder S. Sethi
Detecting spatial regularity in images arises in computer vision, scene analysis, military appli-cations, and other areas. In this paper we present anO(n 5 2) algorithm that reports all maximal...
Generalized neighbor-joining: more reliable phylogenetic tree reconstruction (1999)
William R. Pearson, Gabriel Robins, Tongtong Zhang
We have developed a phylogenetic tree reconstruction method that detects and reports multiple, topologically distant, low cost solutions. Our method is a generalization of the Neighbor-Joining (NJ)...
On detecting spatial regularity in noisy images (1999)
Gabriel Robins, Brian L. Robinson, Bhupinder S. Sethi, Communicated D. Gries
The ISI (Information Sciences Institute) Grapher Manual. (1998)
This document describes the implementation and usage of the ISI Grapher, a portable software package that allows graphs to be displayed pictorially. The salient features of the ISI Grapher are its...
Applications of the ISI (Information Sciences Institute) Grapher. (1998)
The author describes various end-user applications that were built using the ISI Grapher, a portable software tool for displaying graphs pictorially. She enumerates numerous current research projects...
Filling and Slotting : Analysis and Algorithms (1998)
Andrew Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps -- notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP)-- have varying...
Improved Approximation Bounds for the Group Steiner Problem (1998)
C. S. Helvig, Gabriel Robins, Alexander Zelikovsky
Given a weighted graph and a family of k disjoint groups of nodes, the Group Steiner Problem asks for a minimum-cost routing tree that contains at least one node from each group. We give...
Filling and Slotting : Analysis and Algorithms (1998)
Andrew Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps -- notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP)-- have varying...
Improved Approximation Bounds for the Group Steiner Problem (1998)
Helvig Gabriel Robins, C. S. Helvig, Gabriel Robins, Alexander Zelikovsky
Given a weightedgraph and a family of k disjoint groups of nodes, the Group Steiner Problem asks for a minimum-cost routing tree that contains at least one node from each group. We give...
Filling and Slotting: Analysis and Algorithms (1998)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps – notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP) – have varying...
Moving-target TSP and related problems (1998)
C. S. Helvig, Gabriel Robins, Alex Zelikovsky
Abstract. Previous literature on the Traveling Salesman Problem (TSP) assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent...
Filling and Slotting: Analysis and Algorithms (1998)
Andrew B. Kahng, Gabriel Robins, Anish Singh, Huijuan Wang, Er Zelikovsky
In very deep-submicron VLSI, certain manufacturing steps – notably optical exposure, resist development and etch, chemical vapor deposition and chemical-mechanical polishing (CMP) – have varying...
Placement and Routing for Performance-Oriented FPGA Layout (1998)
Michael J. Alexander, James P. Cohoon, Joseph L. Ganley, Gabriel Robins
This paper presents a performance-oriented placement and routing tool for field-programmable gate arrays. Using recursive geometric partitioning for simultaneous placement and global routing, and a...
Moving-Target TSP and Related Problems (1997)
C. S. Helvig, Gabriel Robins, Alex Zelikovsky
. Previous literature on the Traveling Salesman Problem (TSP) implicitly assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent...
Moving-Target TSP and Related Problems (1997)
C. S. Helvig, Gabriel Robins, Alex Zelikovsky
. Previous literature on the Traveling Salesman Problem (TSP) assumed that the sites to be visited are stationary. Motivated by practical applications, we introduce a time-dependent generalization of...
Provably Good Routing Tree Construction with Multi-Port Terminals (1997)
C. Douglass Bateman, C. S. Helvig, Gabriel Robins, Alexander Zelikovsky, Er Zelikovsky
Previous literature on VLSI routing and wiring estimation typically assumes a one-to-one correspondence between terminals and ports. In practice, however (say, in a gridded routing regime), each...
Placement and Routing for Three-Dimensional FPGAs (1996)
Michael J. Alexander, James P. Cohoon, Jared L. Colflesh, John Karro, Edward L. Peters, Gabriel Robins
We explore physical layout for a three-dimensional (3D) FPGA architecture. For placement, we introduce a topdown partitioning technique based on rectilinear Steiner trees; we then employ a one-step...
On the Primer Selection Problem in Polymerase Chain Reaction Experiments (1996)
William R. Pearson, Gabriel Robins, Dallas E. Wrege, Tongtong Zhang
In this paper we address the problem of primer selection in polymerase chain reaction (PCR) experiments. We prove that the problem of minimizing the number of primers required to amplify a set of DNA...
New Performance-Driven FPGA Routing Algorithms (1996)
Michael J. Alexander, Gabriel Robins
Motivated by the goal of increasing the performance of FPGA-based designs, we propose effective Steiner and arborescence FPGA routing algorithms. Our graphbased Steiner tree constructions have...
New Performance-Driven FPGA Routing Algorithms (1996)
Michael J. Alexander, Gabriel Robins
Motivated by the goal of increasing the performance of FPGA-based designs, we propose new Steiner and arborescence FPGA routing algorithms. Our Steiner tree constructions significantly outperform the...
Near-Optimal Critical Sink Routing Tree Constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "Global Slack...
Performance-Oriented Placement and Routing for Field-Programmable Gate Arrays (1995)
Michael J. Alexander, James P. Cohoon, Joseph L. Ganley, Gabriel Robins
This paper presents a performance-oriented placement and routing tool for field-programmable gate arrays. Using recursive geometric partitioning for simultaneous placement and global routing, and a...
A New Approach to Primer Selection in Polymerase Chain Reaction Experiments (1995)
William Pearson, Gabriel Robins
We address the problem of primer selection in polymerase chain reaction (PCR) experiments. We prove that the problem of minimizing the number of primers required to amplify a set of DNA sequences is...
Three-Dimensional Field-Programmable Gate Arrays (1995)
Michael J. Alexander, James P. Cohoon, Jared L. Colflesh, John Karro, Gabriel Robins
Motivated by improving FPGA performance, we propose a new three-dimensional (3D) FPGA architecture, along with a fabrication methodology. We analyze the expected manufacturing yield, and raise...
Pattern Minefield Detection from Inexact Data (Extended Abstract) (1995)
Gabriel Robins, Brian L. Robinson
Detecting spatial regularity in images arises in military applications, computer vision, scene analysis, and other areas. In this paper we give a O(n 5=2 )-time algorithm that for a given pointset...
Geometric Interconnection and Placement Algorithms (1995)
Joseph Lavinus Ganley, Joseph L. Ganley, Jeffrey S. Salowe, Gabriel Robins, ...
This dissertation examines a number of geometric interconnection, partitioning, and placement problems arising in the field of VLSI physical design automation. In particular, many of the results...
Bernard A. Mccoy, Gabriel Robins
An implicit premise of existing routing methods is ihat the routing topology must correspond to a tree (i.e., it does not contain cycles). In this paper we rnvestigate the consequences of abandoning...
Near-optimal critical sink routing tree constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Associate Member, Bernard A. Mccoy, Gabriel Robins
Abstract-We present critical-sink routing tree (CSRT) con-structions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and “global slack...
Near-optimal critical sink routing tree constructions (1995)
Kenneth D. Boese, Andrew B. Kahng, Associate Member, Bernard A. Mccoy, Gabriel Robins
Abstract-We present critical-sink routing tree (CSRT) constructions which exploit available critical-path information to yield high-performance routing trees. Our CS-Steiner and "global...
An Architecture-Independent Approach to FPGA Routing Based on (1994)
Michael J. Alex, James P. Cohoon, Joseph L. Ganley, Gabriel Robins
We propose a general framework for FPGA routing, which allows simultaneous optimization of multiple competing objectives under a smooth designercontrolled tradeoff. Our approach is based on a new...
On the Maximum Degree of Minimum Spanning Trees (1994)
Gabriel Robins, Gabriel Robins, Jeffrey S. Salowe, Jeffrey S. Salowe
Motivated by practical VLSI applications, we study the maximum vertex degree in a minimum spanning tree (MST) under arbitrary L p metrics. We show that the maximum vertex degree in a maximum-degree L...
Rectilinear Steiner Trees with Minimum Elmore Delay (1994)
Kenneth Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We provide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of...
Dynamically-Wiresized Elmore-Based Routing Constructions (1994)
Todd D. Hodes, Bernard A. Mccoy, Gabriel Robins
We analyze the impact of wiresizing on the performance of Elmore-based routing constructions. Whereas previous wiresizing schemes are static (i.e., they wiresize an existing topology), we introduce a...
Rectilinear Steiner Trees with Minimum Elmore Delay (1994)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We provide a new theoretical framework for constructing Steiner routing trees with minimum Elmore delay. Earlier work [3, 13] has established Elmore delay as a high fidelity estimate of...
On the Maximum Degree of Minimum Spanning Trees (1994)
Gabriel Robins, Jeffrey S. Salowe
Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that under the L p norm, the maximum vertex degree over all MSTs is...
Dynamically-Wiresized Elmore-Based Routing Constructions (1994)
Todd Hodes, Bernard A. Mccoy, Gabriel Robins
We analyze the impact of wiresizing on the performance of Elmore-based routing constructions. Whereas previous wiresizing schemes are static (i.e., they wiresize an existing topology), we introduce a...
Dynamically-Wiresized Elmore-Based Routing Constructions (1994)
Todd Hodes, Bernard A. Mccoy, Gabriel Robins
We analyze the impact of wiresizing on the performance of Elmore-based routing constructions. Whereas previous wiresizing schemes are static (i.e., they wiresize an existing topology), we introduce a...
Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time (1994)
Jeff Griffith, Gabriel Robins, Jeffrey S. Salowe, Tongtong Zhang
The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing...
Bernard A. Mccoy, Gabriel Robins
An implicit premise of existing routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). In this paper we investigate the consequences of abandoning...
An implicit premise of existing routing methods is that the routing topology must correspond to a tree (i.e., it does not contain cycles). In this paper we investigate the consequences of abandoning...
Matching-based methods for high-performance clock routing (1993)
Jason Cong, Andrew B. Kahng, Associate Member, Gabriel Robins
Abstract--Minimizing clock skew is important in the design of high performance VLSI systems. We present a general clock routing scheme that achieves very small clock skews while still using a...
Toward Optimal Routing Trees (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delay properties. We begin from first principles, and study the accuracy and fidelity of easily-computed delay models...
High-performance routing trees with identified critical sinks (1993)
Kenneth D. Boese, Kenneth D. Boese, Andrew B. Kahng, Andrew B. Kahng, Gabriel Robins, Gabriel Robins
We present critical-sink routing tree (CSRT) constructions which yield high-performance routing trees by exploiting the critical-path information that may be available during timing-driven layout....
An Architecture-Independent Unified Approach to FPGA Routing (1993)
Michael J. Alexander, Gabriel Robins
Field-programmable gate arrays (FPGAs) are an inexpensive and flexible "low risk" design alternative to custom integrated circuits. While FPGA partitioning and technology mapping have been...
Toward Optimal Routing Trees (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delay properties. We begin from first principles, and study the accuracy and fidelity of easily-computed delay models...
Optimal Robust Path Planning in General Environments (1993)
T. C. Hu, Andrew B. Kahng, Gabriel Robins
We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach which...
Fidelity and Near-Optimality of Elmore-Based Routing Constructions (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delays. We study the accuracy and fidelity of easily-computed delay models with respect to detailed simulation (e.g.,...
High-Performance Routing Trees With Identified Critical Sinks (1993)
Kenneth Boese, Andrew B. Kahng, Gabriel Robins
We present two critical-sink routing tree (CSRT) constructions which exploit critical-path information that becomes available during timing-driven layout. Our CS-Steiner heuristics with "Global...
Tim Barrera, Jeff Griffith, Sally A. Mckee, Gabriel Robins, Tongtong Zhang
The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NP-hard, and the best performing...
On the Primer Selection Problem in Polymerase Chain Reaction Experiments (1993)
Gabriel Robins, Dallas E. Wrege, Tongtong Zhang, William R. Pearson
In this paper we address the problem of primer selection in polymerase chain reaction (PCR) experiments. We prove that the problem of minimizing the number of primers required to amplify a set of DNA...
Optimal Robust Path Planning in General Environments (1993)
T. C. Hu, Andrew B. Kahng, Gabriel Robins
We address robust path planning for a mobile agent in a general environment by finding minimum cost source-destination paths having prescribed widths. The main result is a new approach which...
Fidelity and Near-Optimality of Elmore-Based Routing Constructions (1993)
Kenneth D. Boese, Andrew B. Kahng, Bernard A. Mccoy, Gabriel Robins
We address the efficient construction of interconnection trees with near-optimal delays. We study the accuracy and fidelity of easily-computed delay models with respect to detailed simulation (e.g.,...
High-Performance Routing Trees With Identified Critical Sinks (1993)
Kenneth Boese, Andrew B. Kahng, Gabriel Robins
We present two critical-sink routing tree (CSRT) constructions which exploit critical-path information that becomes available during timing-driven layout. Our CS-Steiner heuristics with "Global...
Toward a Steiner Engine: Enhanced Serial and Parallel (1993)
Tim Barrera, Jeff Griffith, Sally A. Mckee, Gabriel Robins, Tongtong Zhang
The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estima-tion, as well as in many other areas. The MRST problem is known to be NP-hard, and the best perform-ing...
Matching-based methods for high-performance clock routing (1993)
Jason Cong, Andrew B. Kahng, Associate Member, Gabriel Robins
Abstract-Minimizing clock skew is important in the design of high performance VLSI systems. We present a general clock routing scheme that achieves very small clock skews while still using a...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract-We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius mini-mum routing tree...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract--We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree...
A new class of iterative Steiner tree heuristics with good performance (1992)
Andrew B. Kahng, Associate Member, Gabriel Robins, Student Member
problem is very important for such aspects of physical layout as global routing and wiring estimation. Virtually all previous heuristics for computing rectilinear Steiner trees begin with a minimum...
Tim Barrera, Tim Barrera, Jeff Griffith, Jeff Griffith, Sally A. Mckee, Sally A. Mckee, ...
The minimum rectilinear Steiner tree (MRST) problem arises in global routing and wiring estimation, as well as in many other areas. The MRST problem is known to be NPhard, and the best performing...
Provably good performance-driven global routing (1992)
Jingsheng Cong, Andrew B. Kahng, Associate Member, Gabriel Robins, Majid Sarrafzadeh, C. K. Wong
Abstract-We propose a provably good performance-driven global routing algorithm for both cell-based and building-block design. The approach is based on a new bounded-radius minimum routing tree...
A new class of iterative Steiner tree heuristics with good performance (1992)
Andrew B. Kahng, Associate Member, Gabriel Robins, Student Member
problem is very important for such aspects of physical layout as global routing and wiring estimation. Virtually all previous heuristics for computing rectilinear Steiner trees begin with a minimum...
ORGANIZATION (If applicable) (1988)
This document is approved for public release, 2b. DECLASSIFICATION I DOWNGRADING SCHEDULE distribution is unlimited.
Reprinted from the Proceedings of Symboliikka "87,
Recent Developments in NIKL (1986)
Thomas S. Kaczmarek, Raymond Bates, Gabriel Robins
ABSTRACT This paper will concentrate on enhancements made to the expressiveness of NIKL but will also describe some improvements NIKL (a New Implementation of KL-ONE) is one of the members and...
Filling Algorithms and Analyses for Layout Density Control
Andrew B. Kahng, Gabriel Robins, Anish Singh, Alexander Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying effects on device and interconnect features, depending on local characteristics of the...
Placement and Routing for Performance-Oriented FPGA Layout
Michael J. Alexander, James P. Cohoon, Joseph L. Ganley, Gabriel Robins
This paper presents a performance-oriented placement and routing tool for field-programmable gate arrays. Using recursive geometric partitioning for simultaneous placement and global routing, and a...