Solving VLSI design and DNA sequencing problems using bipartization of graphs
Mahjoub, Ali Ridha; Fouilhoux, Pierre (2012), Solving VLSI design and DNA sequencing problems using bipartization of graphs, Computational Optimization and Applications, 51, 2, p. 749-781. http://dx.doi.org/10.1007/s10589-010-9355-1
TypeArticle accepté pour publication ou publié
Journal nameComputational Optimization and Applications
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsGenomics; Electronics; Polyhedral approach; Branch-and-cut algorithm; Bipartite induced subgraph problem
Showing items related by title and author.
The multilayer capacitated survivable IP network design problem: valid inequalities and branch-and-cut Fouilhoux, Pierre; Klopkenstein, Olivier; Mahjoub, Ali Ridha; Borne, S. (2009) Communication / Conférence
The Two-Edge Connected Hop-Constrained Network Design Problem : Valid Inequalities and Branch-and-Cut Pesneau, Pierre; Mahjoub, Ali Ridha; Labbé, Martine; Huygens, David (2007) Article accepté pour publication ou publié