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, which is NP-hard in general. 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 algorithm. We also provide direct optimal solutions for special trees like stars and paths.
Optimal shift coloring of trees
SERAFINI, Paolo
2014-01-01
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, which is NP-hard in general. 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 algorithm. We also provide direct optimal solutions for special trees like stars and paths.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
