• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

The maximum induced bipartite subgraph problem with edge weights

Cornaz, Denis; Mahjoub, Ali Ridha (2007), The maximum induced bipartite subgraph problem with edge weights, SIAM Journal on Discrete Mathematics, 21, 3, p. 662-675. http://dx.doi.org/10.1137/060650015

Type
Article accepté pour publication ou publié
Date
2007
Journal name
SIAM Journal on Discrete Mathematics
Volume
21
Number
3
Publisher
SIAM
Pages
662-675
Publication identifier
http://dx.doi.org/10.1137/060650015
Metadata
Show full item record
Author(s)
Cornaz, Denis
Mahjoub, Ali Ridha
Abstract (EN)
Given a graph $G=(V,E)$ with nonnegative weights on the edges, the maximum induced bipartite subgraph problem (MIBSP) is to find a maximum weight bipartite subgraph $(W,E[W])$ of $G$. Here $E[W]$ is the edge set induced by $W$. An edge subset $F\subseteq E$ is called independent if there is an induced bipartite subgraph of $G$ whose edge set contains $F$. Otherwise, it is called dependent. In this paper we characterize the minimal dependent sets, that is, the dependent sets that are not contained in any other dependent set. Using this, we give an integer linear programming formulation for MIBSP in the natural variable space, based on an associated class of valid inequalities called dependent set inequalities. Moreover, we show that the minimum dependent set problem with nonnegative weights can be reduced to the minimum circuit problem in a directed graph, and can then be solved in polynomial time. This yields a polynomial-time separation algorithm for the dependent set inequalities as well as a polynomial-time cutting plane algorithm for solving the linear relaxation of the problem. We also discuss some polyhedral consequences.
Subjects / Keywords
Separation algorithm; Minimal dependent set; Edge weight; induced bipartite subgraph

Related items

Showing items related by title and author.

  • Thumbnail
    Polyhedral results for the bipartite induced subgraph problem 
    Fouilhoux, Pierre; Mahjoub, Ali Ridha (2006) Article accepté pour publication ou publié
  • Thumbnail
    Two-edge connected subgraph with bounded rings problem: Polyhedral results and Branch-and-Cut 
    Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié
  • Thumbnail
    The k-edge subgraph problem I: Critical extreme points 
    Didi Biha, Mohamed; Mahjoub, Ali Ridha (2004) Article accepté pour publication ou publié
  • Thumbnail
    A Branch-and-Cut algorithm for the k-edge connected subgraph problem 
    Mailfert, Jean; Mahjoub, Ali Ridha; Didi Biha, Mohamed; Ibrahima, Diarrassouba; Bendali, Fatiha (2010) Article accepté pour publication ou publié
  • Thumbnail
    Optimiser sur les ensembles d'arêtes des graphes bipartis induits 
    Mahjoub, Ali Ridha; Cornaz, Denis (2009) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo