The Maximum Induced Bipartite Subgraph Problem with Edge Weights

DOI10.1137/060650015MaRDI QIDQ3519200zbMATH OpenOpenAlexFDO

Authors Denis Cornaz, A. R. Mahjoub

Publication date 13 August 2008

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/aaf0ea18065c19aad2a2ee4a40e9678e9844b7cd

zbMATH Keywords

edge weightinduced bipartite subgraphminimal dependent setpolytopeseparation algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Polyhedral results for the bipartite induced subgraph problem
• Compositions in the bipartite subgraph polytope
• On co-bicliques
• A linear programming formulation for the maximum complete multipartite subgraph problem
• Perfectly matchable subgraph problem on a bipartite graph

Cited in

(15)

• Compositions in the bipartite subgraph polytope
• Minimal arc-sets spanning dicycles
• The minimum chromatic violation problem: a polyhedral approach
• Polyhedral results for the bipartite induced subgraph problem
• Boundary graph classes for some maximum induced subgraph problems
• A linear programming formulation for the maximum complete multipartite subgraph problem
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Cycle transversals in bounded degree graphs
• On co-bicliques
• Perfectly matchable subgraph problem on a bipartite graph
• The Maximum Weight Connected Subgraph Problem
• Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs
• Mixed-Integer Vertex Covers on Bipartite Graphs
• Maximum bipartite subgraphs of geometric intersection graphs
• Maximum weighted edge biclique problem on bipartite graphs

This page was built for publication: The Maximum Induced Bipartite Subgraph Problem with Edge Weights

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