Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "1057"
  #_source: array:26 [
    "id" => "1057"
    "slug" => "edge-cover-by-connected-bipartite-subgraphs"
    "yearMonth" => "2011-09"
    "year" => "2011"
    "title" => "Edge Cover by Connected Bipartite Subgraphs"
    "description" => "LIBERTI, L., ALFANDARI, L. et PLATEAU, M.C. (2011). Edge Cover by Connected Bipartite Subgraphs. <i>Annals of Operations Research</i>, 188(1), pp. 307-329."
    "authors" => array:3 [
      0 => array:3 [
        "name" => "ALFANDARI Laurent"
        "bid" => "B00000901"
        "slug" => "alfandari-laurent"
      ]
      1 => array:1 [
        "name" => "LIBERTI L."
      ]
      2 => array:1 [
        "name" => "PLATEAU M.-C."
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:5 [
      0 => "Local Search"
      1 => "Bipartite Graph"
      2 => "Vertex Cover"
      3 => "Constructive Heuristic"
      4 => "Edge Cover"
    ]
    "updatedAt" => "2021-02-02 16:16:18"
    "publicationUrl" => "https://link.springer.com/article/10.1007/s10479-009-0533-4"
    "publicationInfo" => array:3 [
      "pages" => "307-329"
      "volume" => "188"
      "number" => "1"
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "Le problème étudié consiste à couvrir les arêtes d'un graphe par un nombre minimum de sous-graphes bipartis connexes. Nous montrons que ce problème est NP-difficile, proposons des bornes inférieures via une formulation de type programmation mathématique en nombres entiers, ainsi que plusieurs heuristiques constructives et de recherche locale comparées via des expérimentations numériques."
      "en" => "We consider the problem of covering the edge set of an unweighted, undirected graph with the minimum number of connected bipartite subgraphs (where the subgraphs are not necessarily bicliques).We show that this is an NP-hard problem, provide lower bounds through an IP formulation, propose several constructive heuristics and a local search, and discuss computational results. Finally, we consider a constrained variant of the problem which we show to be NP-hard, and provide an IP formulation for the variant."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-11-21T10:21:50.000Z"
    "docTitle" => "Edge Cover by Connected Bipartite Subgraphs"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/alfandari-laurent">ALFANDARI Laurent</a>, LIBERTI L., PLATEAU M.-C."
    "docDescription" => "<span class="document-property-authors">ALFANDARI Laurent, LIBERTI L., PLATEAU M.-C.</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2011</span>"
    "keywordList" => "<a href="#">Local Search</a>, <a href="#">Bipartite Graph</a>, <a href="#">Vertex Cover</a>, <a href="#">Constructive Heuristic</a>, <a href="#">Edge Cover</a>"
    "docPreview" => "<b>Edge Cover by Connected Bipartite Subgraphs</b><br><span>2011-09 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://link.springer.com/article/10.1007/s10479-009-0533-4" target="_blank">Edge Cover by Connected Bipartite Subgraphs</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 9.064929
  +"parent": null
}