- Sum Edge Coloring on Multigraphs
- Project Year:
2020
- REU Student (s):
Hongyi Hu | Carnegie Mellon University PA
- Student 1 Institution:
Carnegie Mellon University
- Project Mentor:
Atefeh Mohajeri
- Project Mentor Area:
Math and Algorithmic Group - Nokia Bell Labs
- Project Abstract:
We study sum edge coloring for multigraphs, motivated by the bi-processor scheduling problem; the jobs must be scheduled in such a way that no two jobs that share a processor may run at the same time and the average completion time is minimized. If edges are jobs and vertices processors, then the scheduling problem is precisely edge coloring with the intention to minimize the sum over all colors used. We investigate two variants of sum coloring: the Minimum Edge Chromatic Sum (MECS) problem and the Optimum Cost Chromatic Partition (OCCP) problem. The former aims to find an edge coloring that minimizes the sum of the maximum color on each edge while the latter the sum of all colors used. Despite similarity of the two objectives, they are quite different in complexity. This difference is most observable when restricted to trees; we show that the former remains NP-hard, while the latter is polynomially solvable.
