Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "10918"
  #_source: array:26 [
    "id" => "10918"
    "slug" => "the-maximum-clique-interdiction-problem"
    "yearMonth" => "2019-02"
    "year" => "2019"
    "title" => "The Maximum Clique Interdiction Problem"
    "description" => "FURINI, F., LJUBIC, I., MARTIN, S. et SAN SEGUNDO, P. (2019). The Maximum Clique Interdiction Problem. <i>European Journal of Operational Research</i>, 277(1), pp. 112-127."
    "authors" => array:4 [
      0 => array:3 [
        "name" => "LJUBIC Ivana"
        "bid" => "B00683004"
        "slug" => "ljubic-ivana"
      ]
      1 => array:1 [
        "name" => "FURINI Fabio"
      ]
      2 => array:1 [
        "name" => "MARTIN Sébastien"
      ]
      3 => array:1 [
        "name" => "SAN SEGUNDO Pablo"
      ]
    ]
    "ouvrage" => ""
    "keywords" => array:5 [
      0 => "Combinatorial optimization"
      1 => "Interdiction problems"
      2 => "Maximum clique"
      3 => "(Social) Network analysis"
      4 => "Most vital vertices"
    ]
    "updatedAt" => "2021-09-24 10:33:27"
    "publicationUrl" => "https://doi.org/10.1016/j.ejor.2019.02.028"
    "publicationInfo" => array:3 [
      "pages" => "112-127"
      "volume" => "277"
      "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" => "Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We propose an integer linear programming formulation of the problem based on an exponential family of Clique-Interdiction Cuts and we give necessary and sufficient conditions under which these cuts are facet-defining. Our new approach provides a useful tool for analyzing the resilience of (social) networks with respect to clique-interdiction attacks, i.e., the decrease of the size of the maximum clique as a function of an incremental interdiction budget level. On a benchmark set of publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges, we show that most of them can be analyzed and solved to proven optimality within short computing time."
      "en" => "Given a graph G and an interdiction budget k, the Maximum Clique Interdiction Problem asks to find a subset of at most k vertices to remove from G so that the size of the maximum clique in the remaining graph is minimized. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We propose an integer linear programming formulation of the problem based on an exponential family of Clique-Interdiction Cuts and we give necessary and sufficient conditions under which these cuts are facet-defining. Our new approach provides a useful tool for analyzing the resilience of (social) networks with respect to clique-interdiction attacks, i.e., the decrease of the size of the maximum clique as a function of an incremental interdiction budget level. On a benchmark set of publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges, we show that most of them can be analyzed and solved to proven optimality within short computing time."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-12-03T16:21:42.000Z"
    "docTitle" => "The Maximum Clique Interdiction Problem"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, FURINI Fabio, MARTIN Sébastien, SAN SEGUNDO Pablo"
    "docDescription" => "<span class="document-property-authors">LJUBIC Ivana, FURINI Fabio, MARTIN Sébastien, SAN SEGUNDO Pablo</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">2019</span>"
    "keywordList" => "<a href="#">Combinatorial optimization</a>, <a href="#">Interdiction problems</a>, <a href="#">Maximum clique</a>, <a href="#">(Social) Network analysis</a>, <a href="#">Most vital vertices</a>"
    "docPreview" => "<b>The Maximum Clique Interdiction Problem</b><br><span>2019-02 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1016/j.ejor.2019.02.028" target="_blank">The Maximum Clique Interdiction Problem</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 8.758475
  +"parent": null
}