Abstract — The search for the association between complex diseases and single nucleotide polymorphisms (SNPs) or haplotypes has recently received great attention. For these studies, it is essential...
Practical Approximations of Steiner Trees in Uniform Orientation Metrics (2009)
Andrew B. Kahng, Ion Măndoiu, Er Zelikovsky
The Steiner minimum tree problem, which asks for a minimum-length interconnection of a given set of termi-nals in the plane, is one of the fundamental problems in Very Large Scale Integration (VLSI)...
Problem Formulation Our Solution (2008)
Qiong Cheng Alex, Er Zelikovsky
The Homeomorphism problem of pair wise graphs has been a open problem in the theory of graph. There have been lots of applications which can be reducible to the problem. We aims to propose a feasible...
Greedy Approach to Reliable Disease Susceptibility Prediction (2008)
Dumitru Brinza, Irina Astrovskaya, Er Zelikovsky
Abstract. One of the main problems in genetic epidemiology is to robustly predict genetic susceptibility to complex diseases based on the data from case/control studies. This becomes computationally...
Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees (2008)
Piotr Berman, Martin Fürer Alex, Er Zelikovsky
The Steiner tree problem in unweighted graphs requires to find a minimum size connected subgraph containing a given subset of nodes (terminals). In this paper we investigate applications of the...
Minimum-Buffered Routing of Non-Critical Nets forSlew Rate and Reliability Control \Lambda (2008)
Charles Alpert, Andrew B. Kahng, Bao Liu, Ion M, Er Zelikovsky
ffl We give linear-time algorithms for optimal buffering of a givenrouting tree with a single (inverting or non-inverting) buffer type. ffl For simultaneous routing and buffering with a single...
ABSTRACT Fill for Shallow Trench Isolation CMP (2008)
Andrew B. Kahng, Puneet Sharma, Er Zelikovsky
Shallow trench isolation (STI) is the mainstream CMOS isolation technology. It uses chemical mechanical planarization (CMP) to remove excess of deposited oxide and attain a planar surface for...
1 Optimization Methods for Genotype Data Analysis in Epidemiological Studies (2008)
Dumitru Brinza, Jingwu He, Er Zelikovsky
Recent improvement in accessibility of high-throughput DNA sequencing brought a great deal of attention to disease association and susceptibility studies. Successful genome-wide searches for...
BACKGROUND Linear Programming for Protein-Protein Interaction Prediction (2008)
Gulsah Altun, Stefan Gremalschi, Robert W. Harrison, Er Zelikovsky
has been assumed that protein families that interact with each other must
Area Fill Generation With Inherent Data Volume Reduction \Lambda (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, Er Zelikovsky, Yuhong Zheng
18 OPTIMIZATION METHODS FOR GENOTYPE DATA ANALYSIS IN EPIDEMIOLOGICAL STUDIES (2008)
Dumitru Brinza, Jingwu He, Er Zelikovsky
Recent improvement in accessibility of high throughput DNA sequencing brought a great deal of attention to disease association and susceptibility studies. Successful genome-wide searches for...
Multicommodity Flow Algorithms for Buffered Global Routing (2008)
Christoph Albrecht, Andrew B. Kahng, Ion Măndoiu, Er Zelikovsky
Due to delay scaling effects in deep-submicron technologies, interconnect planning and synthesis are becoming critical to meeting chip performance targets with reduced design turnaround time. In...
2SNP: Scalable Phasing Method for Trios and Unrelated Individuals (2008)
Abstract — Emerging microarray technologies allow affordable typing of very long genome sequences. A key challenge in analyzing of such huge amount of data is scalable and accurate computational...
Case(Control)-Free Multi-SNP Combinations in Case-Control Studies (2008)
Several genome-wide searches for disease-associated gene variations have been recently reported (Spinola et al, 2006; Herbert et al, 2006). However, complex diseases can be caused by combinations of...
Phasing and Missing Data Recovery in Family (2008)
Dumitru Brinza, Jingwu He, Weidong Mao, Er Zelikovsky
Abstract. Although there exist many phasing methods for unrelated adults or pedigrees, phasing and missing data recovery for data representing family trios is lagging behind. This paper is an attempt...
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...
Haplotype Tagging using Support Vector Machines (2008)
Jingwu He, Jun Zhang, Gulsah Altun, Er Zelikovsky, Yanqing Zhang
Abstract — Constructing a complete human haplotype map can help in associating complex diseases with SNPs (single nucleotide polymorphisms). Unfortunately, the number of SNPs is very large and it...
Mapping and Filling Metabolic Pathways (2008)
Qiong Cheng, Dipendra Kaur, Robert Harrison, Er Zelikovsky
Abstract. Network mappings are extensively used for comparing, exploring, and predicting biological networks, are essential for pathway database search and also helpful for finding and filling...
Summary: 2SNP software package implements a new very fast scalable algorithm for haplotype inference based on genotype statistics collected only for pairs of SNPs. This software can be used for...
Qiong Cheng, Robert Harrison, Er Zelikovsky
Network mapping is a convenient tool for comparing and exploring biological networks; it can be used for predicting unknown pathways, fast and meaningful searching of databases, and potentially...
ABSTRACT Fill for Shallow Trench Isolation CMP (2008)
Andrew B. Kahng, Puneet Sharma, Er Zelikovsky
Shallow trench isolation (STI) is the mainstream CMOS isolation technology. It uses chemical mechanical planarization (CMP) to remove excess of deposited oxide and attain a planar surface for...
In this paper we analyze the SNP data (GAW Problem Set 2) for rheumatoid arthritis (RA) trying to check if it is caused by combinations of several unlinked gene variations. We apply here improved...
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...
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...
Abstract Area Fill Generation With Inherent Data Volume Reduction (2008)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, 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....
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...
Practical Approximation Algorithms for Separable Packing Linear Programs (2008)
Feodor F. Dragan, Andrew B. Kahn, Ion I. Mandoiu, Sudhakar Muddu, Alexander Zelikovsky, Er Zelikovsky
We describefVkw polynomial time approximation schemes fm generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Bu#er Blocks (GRBB). We extend...
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract---To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
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...
Abstract Area Fill Generation With Inherent Data Volume Reduction (2007)
Yu Chen, Andrew B. Kahng, Gabriel Robins Alex, 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....
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...
A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence (2007)
Réka Albert, Bhaskar Dasgupta, Riccardo Dondi, Eduardo Sontag, Er Zelikovsky, Kelly Westbrooks
Abstract. In this paper we introduce a new method of combined synthesis and inference of biological signal transduction networks. A main idea of our method lies in representing observed causal...
A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence (2007)
Réka Albert, Bhaskar Dasgupta, Riccardo Dondi, Sema Kachalo, Eduardo Sontag, Er Zelikovsky, ...
Abstract. In this paper we introduce a new method of combined synthesis and inference of biological signal transduction networks. A main idea of our method lies in representing observed causal...
Optimal mapping of multi source trees into dag in biological network (2007)
Abstract. The effective and efficient prediction and reconstruction of biological networks for a variety of inter-species and intra-species organisms have been a challenging research topic in...
Combinatorial Methods for Disease Association Search and Susceptibility Prediction (2006)
Abstract. Accessibility of high-throughput genotyping technology makes possible genome-wide association studies for common complex diseases. When dealing with common diseases, it is necessary to...
Combinatorial Search Methods for Multi-SNP Disease Association (2006)
Dumitru Brinza, Jingwu He, Er Zelikovsky
Abstract — Recent improvements in the accessibility of highthroughput genotyping have brought a deal of attention to genome-wide association studies for common complex diseases. Although, such...
Jingwu He, Er Zelikovsky, Martin Bishop
Summary: The search for the association between complex diseases and single nucleotide polymorphisms (SNPs) or haplotypes has recently received great attention. For these studies, it is essential to...
Genotype Susceptibility and Integrated Risk Factors for Complex Diseases (2006)
Weidong Mao, Dumitru Brinza, Nisar Hundewale, Stefan Gremalschi, Er Zelikovsky
Abstract — Recent improvements in the accessibility of highthroughput genotyping have brought a great deal of attention to disease association and susceptibility studies. This paper explores...
Zelikovsky A: Phasing of 2-SNP Genotypes based on Non-Random Mating Model (2006)
Abstract. Emerging microarray technologies allow genotyping of long genome sequences resulting in huge amount of data. A key challenge is to provide an accurate phasing of very long single nucleotide...
Combinatorial Methods for Disease Association Search and Susceptibility Prediction (2006)
Abstract. Accessibility of high-throughput genotyping technology makes possible genome-wide association studies for common complex diseases. When dealing with common diseases, it is necessary to...
Gruia Calinescu, Sanjiv Kapoor, Er Zelikovsky, Antti Hyvärinen
In ad-hoc wireless networks, certain network connectivity constraints are of interest because of their practical importance. An example of such a constraint would be strong connectivity. The aim is...
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...
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...
Integrated design flow for universal DNA tag arrays (2005)
Nisar Hundewale, Ion M, Claudia Prăjescu, Er Zelikovsky
tools
Linear Reduction Method for Predictive and Informative Tag SNP (2005)
Jingwu He, Kelly Westbrooks, Er Zelikovsky
Constructing a complete human haplotype map is helpful when associating complex dis-eases with their related SNPs. Unfortunately, the number of SNPs is very large and it is costly to sequence many...
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...
Provably good global buffering by multiterminal multicommodity flow approximation (2001)
Feodor F. Dragan, Andrew B. Kahng, Sudhakar Muddu, Er Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and performance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Minimum-buffered routing of non-critical nets for slew rate and reliability control (2001)
Charles Alpert, Andrew B. Kahng, Bao Liu, Ion Măndoiu, Er Zelikovsky
In high-speed digital VLSI design, bounding the load capacitance at gate outputs is a well-known methodology to improve coupling noise immunity, reduce degradation of signal transition edges, and...
New graph bipartizations for doubleexposure, bright field alternating phase-shift mask layout (2001)
Andrew B. Kahng, Shailesh Vaya, Er Zelikovsky
Abstract — We describe new graph bipartization algorithms for layout modification and phase assignment of bright-field alternating phaseshifting masks (AltPSM) [25]. The problem of layout...
New graph bipartizations for doubleexposure, bright field alternating phase-shift mask layout (2001)
Andrew B. Kahng, Shailesh Vaya, Er Zelikovsky
Abstract--- We describe new graph bipartization algorithms for layout modification and phase assignment of bright-field alternating phaseshifting masks (AltPSM) [25]. The problem of layout...
Hierarchical Dummy Fill for Process Uniformity (2001)
Yu Chen, Gabriel Robins Z, Er Zelikovsky
Abstract | To improve manufacturability and performance predictability, we seek to make alayout uniform with respect to prescribed density criteria, by inserting \ ll " geometries into the...
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...
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...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Ion M, Alexander Zelikovsky, Sudhakar Muddu, ...
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
Provably Good Global Buffering Using an Available Buffer Block Plan (2000)
Feodor F. Dragan, Andrew B. Kahng, Ion Mandoiu, Sudhakar Muddu, Alexander Zelikovsky, Er Zelikovsky
To implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based ASIC/SOC...
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...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying e ects on device and interconnect features, depending on local characteristics of the...
On the associative-skew clock routing problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
The Associative-Skew Clock Routing Problem (1999)
Yu Chen Andrew, Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
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...
The Associative-Skew Clock Routing Problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Alexander Zelikovsky, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
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 the associative-skew clock routing problem (1999)
Yu Chen, Andrew B. Kahng, Gang Qu, Er Zelikovsky
We introduce the associative skew clock routing problem, which seeks a clock routing tree such that zero skew is preserved only within identified groups of sinks. The associative skew problem is...
New and Exact Filling Algorithms for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er 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...
On Wirelength Estimations for Row-based Placement (1999)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Er Zelikovsky
Wirelength estimation in VLSI layout is fundamentaltoany pre-detailed routing estimate of timing or routability. In this paper, we develop e cient wirelength estimation techniques appropriate for...
Filling Algorithms and Analyses for Layout Density Control (1999)
Andrew B. Kahng, Gabriel Robins Y, Anish Singh Y, Er Zelikovsky
In very deep-submicron VLSI, manufacturing steps involving chemical-mechanical polishing (CMP) have varying e ects on device and interconnect features, depending on local characteristics of the...
On Wirelength Estimations for Row-Based Placement (1998)
Andrew E. Caldwell, Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Alexander Zelikovsky, Er Zelikovsky
Wirelength estimation in VLSI layout is fundamental to any pre-detailed routing estimate of timing or routability. In this paper, we develop efficient wirelength estimation techniques appropriate for...
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...
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...
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...
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...
Approximating Dense Cases of Covering Problems (1997)
Marek Karpinski, Alexander Zelikovsky, Er Zelikovsky
. We study dense instances of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element of the ground set X belongs to at least...
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...