Polyhedral results for the bipartite induced subgraph problem
From MaRDI portal
Publication:2433802
DOI10.1016/j.dam.2005.04.017zbMath1102.68673OpenAlexW2048660463MaRDI 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
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)
Related Items
A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ The minimum chromatic violation problem: a polyhedral approach ⋮ Two generalizations of proper coloring: hardness and approximability ⋮ 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
Uses Software
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
