Optimal shift coloring of trees |
| |
| Authors: | Giovanni Andreatta Luigi De Giovanni Paolo Serafini |
| |
| Institution: | 1. Dipartimento di Matematica, Università di Padova, via Trieste 63, 35121 Padova, Italy;2. Dipartimento di Matematica e Informatica, Università di Udine, viale delle Scienze 206, 33100 Udine, Italy |
| |
| Abstract: | This paper was motivated by the problem of scheduling the openings of pharmacies during week-ends and holiday periods (shifts). The problem can be modeled as a coloring problem on a graph. In this paper we focus on the special case where the underlying graph is a tree, or, more generally, it is endowed with a tree-metric, and we provide a polynomial-time algorithm. We also provide direct optimal solutions for special trees like stars and paths. |
| |
| Keywords: | Graph coloring Shift coloring Trees Polynomial-time algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
