Polyhedral results for the bipartite induced subgraph problem
DOI10.1016/J.DAM.2005.04.017zbMATH Open1102.68673OpenAlexW2048660463MaRDI QIDQ2433802FDOQ2433802
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
Recommendations
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)
Cites Work
- Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
- 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
- Solving VLSI design and DNA sequencing problems using bipartization of graphs
- Wheel inequalities for stable set polytopes
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- Facets of the Bipartite Subgraph Polytope
- Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
- 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\)
Cited In (15)
- 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
- Mixed-Integer Vertex Covers on Bipartite Graphs
Uses Software
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)
