Polyhedral results for the bipartite induced subgraph problem

DOI10.1016/J.DAM.2005.04.017MaRDI QIDQ2433802zbMATH OpenOpenAlexFDO

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

bipartite induced subgraphbranch-and-cutcutfacetliftingpolytopeseparation algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Facets of the Bipartite Subgraph Polytope
• Compositions in the bipartite subgraph polytope
• On the Graph Bisection Cut Polytope
• Small bipartite subgraph polytopes

Cites work

• A characterization of weakly bipartite graphs
• A graph-theoretic via minimization algorithm for two-layer printed circuit boards
• A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Facets of the balanced (acyclic) induced subgraph polytope
• Facets of the Bipartite Subgraph Polytope
• Graph Bipartization and via minimization
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Weakly bipartite graphs and the max-cut problem
• Wheel inequalities for stable set polytopes

Cited in

(15)

• Polyhedral properties of the induced cluster subgraphs
• The minimum chromatic violation problem: a polyhedral approach
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• A combined parallel Lagrangian decomposition and cutting-plane generation for maximum stable set problems
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• Facets of the Bipartite Subgraph Polytope
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Integer programming models for detecting graph bipartitions with structural requirements
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Mixed-Integer Vertex Covers on Bipartite Graphs
• Two generalizations of proper coloring: hardness and approximability
• The maximum k-colorable subgraph problem and orbitopes
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph

Describes a project that uses

Uses Software

• ABACUS

This page was built for publication: Polyhedral results for the bipartite induced subgraph problem

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