Essec\Faculty\Model\Contribution {#2233
  #_index: "academ_contributions"
  #_id: "15866"
  #_source: array:26 [
    "id" => "15866"
    "slug" => "15866-on-the-hardness-of-edge-coloring-problems-associated-with-scheduling"
    "yearMonth" => "2025-06"
    "year" => "2025"
    "title" => "On the Hardness of Edge Coloring Problems Associated with Scheduling"
    "description" => "BARBATO, M., DELLE DONNE, D. et LANCINI, E. (2025). On the Hardness of Edge Coloring Problems Associated with Scheduling. Dans: <i>Beyond Frontiers of Operations Research: Emerging Technologies and Innovative Optimization Paradigms</i>. Cham:  Springer Nature Switzerland, pp. 15-24."
    "authors" => array:3 [
      0 => array:3 [
        "name" => "DELLE DONNE Diego"
        "bid" => "B00788133"
        "slug" => "delle-donne-diego"
      ]
      1 => array:1 [
        "name" => "Barbato Michele"
      ]
      2 => array:1 [
        "name" => "Lancini Emiliano"
      ]
    ]
    "ouvrage" => "Beyond Frontiers of Operations Research: Emerging Technologies and Innovative Optimization Paradigms"
    "keywords" => array:3 [
      0 => "Scheduling Problems"
      1 => "Edge Coloring"
      2 => "Computational complexity"
    ]
    "updatedAt" => "2025-07-23 11:54:24"
    "publicationUrl" => "https://doi.org/10.1007/978-3-031-85894-9_2"
    "publicationInfo" => array:3 [
      "pages" => "15-24"
      "volume" => "14"
      "number" => ""
    ]
    "type" => array:2 [
      "fr" => "Actes d'une conférence"
      "en" => "Conference Proceedings"
    ]
    "support_type" => array:2 [
      "fr" => "Editeur"
      "en" => "Publisher"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "In this work, we introduce several Edge Coloring problems related to scheduling and we study their computational complexity. In particular, we prove that the Concurrent Open Shop Coloring is NP-hard. This problem can be summarized as a unitary-time Open Shop Problem with a hard time horizon constraint, in which the goal is to minimize the total processing time of the tasks. We prove that this problem is NP-hard by reducing it to a new variant of the edge coloring problem, named the Mono-Polychromatic Edge Coloring. We study the feasibility and hardness of this problem, both for the general case and when the underlying graph is bipartite. We show that the latter case is equivalent to the Vertex Coloring Problem."
      "en" => "In this work, we introduce several Edge Coloring problems related to scheduling and we study their computational complexity. In particular, we prove that the Concurrent Open Shop Coloring is NP-hard. This problem can be summarized as a unitary-time Open Shop Problem with a hard time horizon constraint, in which the goal is to minimize the total processing time of the tasks. We prove that this problem is NP-hard by reducing it to a new variant of the edge coloring problem, named the Mono-Polychromatic Edge Coloring. We study the feasibility and hardness of this problem, both for the general case and when the underlying graph is bipartite. We show that the latter case is equivalent to the Vertex Coloring Problem."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2025-12-06T06:21:43.000Z"
    "docTitle" => "On the Hardness of Edge Coloring Problems Associated with Scheduling"
    "docSurtitle" => "Actes d'une conférence"
    "authorNames" => "<a href="/cv/delle-donne-diego">DELLE DONNE Diego</a>, Barbato Michele, Lancini Emiliano"
    "docDescription" => "<span class="document-property-authors">DELLE DONNE Diego, Barbato Michele, Lancini Emiliano</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2025</span>"
    "keywordList" => "<a href="#">Scheduling Problems</a>, <a href="#">Edge Coloring</a>, <a href="#">Computational complexity</a>"
    "docPreview" => "<b>On the Hardness of Edge Coloring Problems Associated with Scheduling</b><br><span>2025-06 | Actes d'une conférence </span>"
    "docType" => "research"
    "publicationLink" => "<a href="https://doi.org/10.1007/978-3-031-85894-9_2" target="_blank">On the Hardness of Edge Coloring Problems Associated with Scheduling</a>"
  ]
  +lang: "fr"
  +"_score": 8.739376
  +"_ignored": array:3 [
    0 => "abstract.en.keyword"
    1 => "abstract.fr.keyword"
    2 => "description.keyword"
  ]
  +"parent": null
}