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

polytopebranch-and-cutcutfacetliftingseparation algorithmbipartite induced subgraph

Mathematics Subject Classification ID

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

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 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
• A min-max relation for \(K_ 3\)-covers in graphs noncontractible to \(K_ 5\backslash e\)
• 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
• 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)

• Mixed-Integer Vertex Covers on Bipartite Graphs
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Two generalizations of proper coloring: hardness and approximability
• The Maximum Induced Bipartite Subgraph Problem with Edge Weights
• The maximum k-colorable subgraph problem and orbitopes
• Integer programming models for detecting graph bipartitions with structural requirements
• Polyhedral properties of the induced cluster subgraphs
• 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
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• Facets of the Bipartite Subgraph Polytope
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• The minimum chromatic violation problem: a polyhedral approach
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs

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)