Solving VLSI design and DNA sequencing problems using bipartization of graphs |
| |
Authors: | Pierre Fouilhoux A Ridha Mahjoub |
| |
Institution: | (3) Center of Applied Optimization, University of Florida, Gainesville, USA; |
| |
Abstract: | In this paper we consider the 2-layer constrained via minimization problem and the SNP haplotype assembly problem. The former
problem arises in the design of integrated and printed circuit boards, and the latter comes up in the DNA sequencing process
for diploid organisms. We show that, for any maximum junction degree, the problem can be reduced to the maximum bipartite
induced subgraph problem. Moreover we show that the SNP haplotype assembly problem can also be reduced to the maximum bipartite
induced subgraph problem for the so-called minimum error correction criterion. We give a partial characterization of the bipartite
induced subgraph polytope. Using this, we devise a branch-and-cut algorithm and report some experimental results. This algorithm
has been used to solve real and large instances. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|