Solving VLSI design and DNA sequencing problems using bipartization of graphs

DOI10.1007/S10589-010-9355-1zbMATH Open1245.90100OpenAlexW2104881193MaRDI QIDQ429453FDOQ429453

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

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

zbMATH Keywords

genomicsbranch-and-cut algorithmpolyhedral approachbipartite induced subgraph problemelectronics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

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

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)