Scholarlink

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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Hardness of Edge Coloring Problems Associated with Scheduling

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Michele Barbato,
  • Diego Delle Donne,
  • Emiliano Lancini

摘要

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.