Polyhedral results for the bipartite induced subgraph problem

DOI10.1016/j.dam.2005.04.017zbMath1102.68673MaRDI QIDQ2433802

Pierre Fouilhoux, Ali Ridha Mahjoub

Publication date: 30 October 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2963

zbMATH Keywords

lifting; polytope; cut; branch-and-cut; facet; separation algorithm; bipartite induced subgraph

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

Solving VLSI design and DNA sequencing problems using bipartization of graphs, The maximum \(k\)-colorable subgraph problem and orbitopes, Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph, A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems

Uses Software

• ABACUS

Cites Work

• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Facets of the balanced (acyclic) induced subgraph polytope
• Weakly bipartite graphs and the max-cut problem
• Wheel inequalities for stable set polytopes
• A characterization of weakly bipartite graphs
• A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
• Facets of the Bipartite Subgraph Polytope
• Graph Bipartization and via minimization
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• 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