Virus Quasispecies Assembly using Network Flows (2009)
Alexander Zelikovsky of Georgia State University presented a lecture on September 25, 2009 at 2:00 pm in room 2443 of the Klaus Advanced Computing Building on the Georgia Tech campus.
Family trio phasing and missing data recovery (2009)
Dumitru Brinza, Jingwu He, Weidong Mao, Alexander 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...
MetNetAligner: a web service tool for metabolic network alignments (2009)
Cheng, Qiong, Harrison, Robert, Zelikovsky, Alexander
Summary: The accumulation of high-throughput genomic, proteomic and metabolical data allows for increasingly accurate modeling and reconstruction of metabolic networks. Alignment of the reconstructed...
ABSTRACT Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as flooding, is to let every node retransmit the message to all...
Family Trio Phasing and Missing Data Recovery ∗ (2008)
Dumitru Brinza, Jingwu He, Weidong Mao, Alexander 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...
Chaitanya Bandela, Ion I. Măndoiu, Yu Chen, Andrew B. Kahng, Alexander Zelikovsky
Abstract. Auctions and exchanges are one of the most important market mechanisms for price determination and allocation of goods. In this paper we consider the case when each buyer has a limited...
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...
Association testing by haplotype-sharing methods applicable to whole-genome analysis (2007)
Nolte, Ilja M, De Vries, André R, Spijker, Geert T, Jansen, Ritsert C, Brinza, Dumitru, Zelikovsky, Alexander, ...
Abstract We propose two new haplotype-sharing methods for identifying disease loci: the haplotype sharing statistic (HSS), which compares length of shared haplotypes between cases and controls, and...
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...
On Approximation of the Power-p and Bottleneck Steiner Trees (2007)
Piotr Berman, Alexander Zelikovsky
Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. 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...
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...
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...
Gruia C Alinescu, Peng-jun Wan, Alexander Zelikovsky
Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as ooding, is to let every node retransmit the message to all its 1-hop...
Gruia C Alinescu, Peng-jun Wan, Alexander Zelikovsky
Broadcasting is a fundamental operation which is frequent in wireless ad hoc networks. A simple broadcasting mechanism, known as ooding, is to let every node retransmit the message to all its 1-hop...
On Approximation of the Power-p and Bottleneck Steiner Trees Piotr (2007)
Many VLSI routing applications, as well as the facility location problem involve computation of Steiner trees with non-linear cost measures. We consider two most frequent versions of this problem. In...
Feodor F. Dragan, Andrew B. Kahng, Ion I. M, Sudhakar Muddu, Alexander Zelikovsky
Abstract. We describe fully polynomial time approximation schemes for generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Buffer Blocks (GRBB). We extend...
Provably Good Global Buffering by Generalized Multiterminal Multicommodity Flow Approximation (2007)
Feodor F. Dragan, Andrew B. Kahng, Ion I. Măndoiu, Sudhakar Muddu, Alexander Zelikovsky
Abstract—To implement high-performance global interconnect without impacting the placement and per-formance of existing blocks, the use of buffer blocks is becoming increasingly popular in...
Association testing by haplotype-sharing methods applicable to whole-genome analysis (2007)
Nolte, Ilja M., Vries, André R. De, Spijker, Geert T., Jansen, Ritsert C., Brinza, Dumitru, Zelikovsky, Alexander, ...
We propose two new haplotype-sharing methods for identifying disease loci: the haplotype sharing statistic (HSS), which compares length of shared haplotypes between cases and controls, and the CROSS...
Réka Albert, Riccardo Dondi, Eduardo Sontag, Kelly Westbrooks, Bhaskar Dasgupta, Sema Kachalo, ...
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 relationships as...
DISCRETE ALGORITHMS FOR ANALYSIS OF GENOTYPE DATA (2007)
Under Direction, Alexander Zelikovsky, Dumitru Brinza
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 search and...
Réka Albert, Riccardo Dondi, Eduardo Sontag, Kelly Westbrooks, Bhaskar Dasgupta, Sema Kachalo, ...
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 relationships as...
A Novel Method for Signal Transduction Network Inference from Indirect Experimental Evidence (2007)
Réka Albert, Bhaskar Dasgupta, Riccardo Dondi, Sema Kachalo, Eduardo Sontag, Alexander Zelikovsky, ...
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 relationships...
Kelly Westbrooks, Under Direction, Alexander Zelikovsky, Kelly Westbrooks, Kelly Anthony Westbrooks, Kelly Westbrooks, ...
Many problems in bioinformatics are inference problems, that is, the problem objective is to infer something based upon a limited amount of information. In this work we explore two different...
He, Jingwu, Zelikovsky, Alexander
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...
2SNP: scalable phasing based on 2-SNP haplotypes (2006)
Brinza, Dumitru, Zelikovsky, Alexander
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...
Family trio phasing and missing data recovery (2005)
Dumitru Brinza, Jingwu He, Weidong Mao, Alexander Zelikovsky
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 to fill...
Multicommodity Flow Algorithms for Buffered Global Routing (2005)
Albrecht, Christoph, Kahng, Andrew B., Mandoiu, Ion I., Zelikovsky, Alexander
In this paper we describe a new algorithm for buffered global routing according to a prescribed buffer site map. Specifically, we describe a provably good multi-commodity flow based algorithm that...
Family trio phasing and missing data recovery (2005)
Dumitru Brinza, Jingwu He, Weidong Mao, Alexander Zelikovsky
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 to fill...
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...
2SNP: scalable phasing based on 2-SNP haplotypes (2005)
Brinza, Dumitru, Zelikovsky, Alexander
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...
Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks (2003)
Gruia Calinescu, Sanjiv Kapoor, Alexander Olshevsky, Alexander Zelikovsky
Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input consists of...
Practical Approximation Algorithms for Zero- and Bounded-Skew Trees (2001)
Alexander Zelikovsky, Ion Mandoiu
The skew of a weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many applications,...
Practical Approximation Algorithms for Zero- and Bounded-Skew Trees (2001)
Alexander Zelikovsky, Ion Mandoiu
The skew of an edge-weighted rooted tree is the maximum difference between any two root-to-leaf path weights. Zero- or bounded-skew trees are needed for achieving synchronization in many...
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...
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...
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...
Kalomire-eleni Mihail, Dana Randall, H. Venkateswaran, Alexander Zelikovsky
This thesis gives improved approximation algorithms and heuristics for several NP-hard problems arising in the global routing phase of physical VLSI design. In each of these problems interconnection...
Approximation Algorithms for VLSI Routing (2000)
Kalomire-eleni Mihail, Dana Randall, H. Venkateswaran, Alexander Zelikovsky
This thesis gives improved approximation algorithms and heuristics for several NP-hard problems arising in the global routing phase of physical VLSI design. In each of these problems interconnection...
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...
Optimal Phase Conflict Removal for Layout of Dark Field Alternating Phase Shifting Masks (1999)
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky
We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following...
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...
Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Alexander Zelikovsky
. Given a graph G with weighted edges, and a subset of nodes T , the T -join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u 2 T . We...
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 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...
Applications of the Matroid Parity Problem to Approximating Steiner Trees (1998)
Martin Furer, Alexander Zelikovsky
The Steiner tree problem in graphs requires to find a minimum size connected subgraph containing a given subset of nodes (given points). In this paper we consider this problem in three classes of...
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...
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...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1998)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first algorithm with a nontrivial approximation ratio for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This...
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...
A series of approximation algorithms for the Acyclic Directed Steiner Tree problem (1997)
Abstract Given an acyclic directed network, a subset S of nodes (terminals), and a root r, the acyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths from r to...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
Approximating Dense Cases of Covering Problems (1997)
Marek Karpinski, Alexander Zelikovsky
We study dense cases 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 belongs to at least fflm sets. We show that the...
Approximating Dense Cases of Covering Problems (1997)
Marek Karpinski, Alexander Zelikovsky
We study dense cases 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 belongs to at least fflm sets. We show that the...
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...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the rst nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-Hard problem of nding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
A New Approximation Algorithm for Finding Heavy Planar Subgraphs (1997)
Gruia Calinescu, Cristina G. Fernandes, Howard Karloff, Alexander Zelikovsky
We provide the first nontrivial approximation algorithm for maximum weight planar subgraph, the NPhard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has...
Better approximation bounds for the network and Euclidean Steiner tree problems (1996)
The network and Euclidean Steiner tree problems require a shortest tree spanning a given vertex subset within a network G = (V; E; d) and Euclidean plane, respectively. For these problems, we present...
Improved Approximations of Maximum Planar Subgraph (1996)
The maximum planar subgraph problem (MPSP) asks for a planar subgraph of a given graph with the maximum total cost. We suggest a new approximation algorithm for the weighted MPSP. We show that it has...
Approximating Dense Cases of Covering Problems (1996)
Marek Karpinski, Alexander Zelikovsky
We study dense cases 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 belongs to at least fflm sets. We show that the...
Approximating Dense Cases of Covering Problems (1996)
Marek Karpinski, Alexander Zelikovsky
We study dense cases 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 belongs to at least fflm sets. We show that the...
Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1995)
Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky
The rectilinear Steiner tree problem requires a shortest tree spanning a given vertex subset in the plane with rectilinear distance. It was proved that the output length of Zelikovsky's [25] and...
New Approximation Algorithms for the Steiner Tree Problems (1995)
Marek Karpinski, Alexander Zelikovsky
The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel...
Marek Karpinski, Alexander Zelikovsky
The Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in a metric space. We suggest a better and fast heuristic for the Steiner problem in graphs and in...
Spanning Closed Trail and Hamiltonian Cycle in Grid Graphs (1995)
Hwan-gue Cho, Alexander Zelikovsky
. In this paper we study a trail routing and a hamiltonian cycle in a class of grid graphs, polycube and polymino. A Spanning closed trail is an eulerian subgraph containing all vertices of a given...
New Approximation Algorithms for the Steiner Tree Problems (1995)
Marek Karpinski, Alexander Zelikovsky
The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel...
The acyclic directed Steiner tree problem (ADSP) requires a minimal outward tree within an acyclic digraph with edge costs G = (V; E; d) which connects a root r with a distinguished subset S ae V ,...
Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1994)
Piotr Berman, Ulrich Fößmeier, Rectilinear Steiner Trees, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky
The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of...
Association testing by haplotype-sharing methods applicable to whole-genome analysis
Nolte, Ilja M, De Vries, André R, Spijker, Geert T, Jansen, Ritsert C, Brinza, Dumitru, Zelikovsky, Alexander, ...
We propose two new haplotype-sharing methods for identifying disease loci: the haplotype sharing statistic (HSS), which compares length of shared haplotypes between cases and controls, and the CROSS...
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...