Solving VLSI design and DNA sequencing problems using bipartization of graphs

DOI10.1007/s10589-010-9355-1zbMath1245.90100OpenAlexW2104881193MaRDI QIDQ429453

Pierre Fouilhoux, Ali Ridha Mahjoub

Publication date: 19 June 2012

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-010-9355-1

zbMATH Keywords

branch-and-cut algorithmgenomicspolyhedral approachbipartite induced subgraph problemelectronics

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Combinatorial optimization (90C27)

Related Items

Mathematical Programming Models and Exact Algorithms, A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, The Maximum k-Colorable Subgraph Problem and Related Problems, Graph Bipartization Problem with Applications to Via Minimization in VLSI Design, Polyhedral results for the bipartite induced subgraph problem, Unnamed Item, A guided tour to computational haplotyping, Maximum Weighted Induced Bipartite Subgraphs and Acyclic Subgraphs of Planar Cubic Graphs, Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem

Cites Work

• Unnamed Item
• Unnamed Item
• Facets of the balanced (acyclic) induced subgraph polytope
• Weakly bipartite graphs and the max-cut problem
• Routing in VLSI-layout
• Compositions in the bipartite subgraph polytope
• Wheel inequalities for stable set polytopes
• A characterization of weakly bipartite graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The haplotyping problem: an overview of computational models and solutions
• Polyhedral results for the bipartite induced subgraph problem
• Facets of the Bipartite Subgraph Polytope
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Graph Bipartization and via minimization
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards