Solving VLSI design and DNA sequencing problems using bipartization of graphs

DOI10.1007/S10589-010-9355-1MaRDI QIDQ429453zbMATH OpenOpenAlexFDO

Authors Pierre Fouilhoux, A. R. 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

genomicsbranch-and-cut algorithmpolyhedral approachbipartite induced subgraph problemelectronics

Mathematics Subject Classification ID

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

Recommendations

• Graph Bipartization and via minimization
• scientific article; zbMATH DE number 1945152
• Via Minimization with Pin Preassignments and Layer Preference
• scientific article; zbMATH DE number 1877046
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

Cites work

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

Cited in

(10)

• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• scientific article; zbMATH DE number 7378704 (Why is no real title available?)
• A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
• Graph Bipartization Problem with Applications to Via Minimization in VLSI Design
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Polyhedral results for the bipartite induced subgraph problem
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Mathematical programming models and exact algorithms
• Characterization of QUBO reformulations for the maximum \(k\)-colorable subgraph problem
• A guided tour to computational haplotyping

This page was built for publication: Solving VLSI design and DNA sequencing problems using bipartization of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q429453)