Categorized bottleneck-Minisum path problems on networks

The authors introduce two path problems on a network, where edges of the network are grouped into categories. The value of a path is calculated by first taking maximum (or sum) of lengths of edges of the path within each category and second taking sum (or maximum) of the obtained values among categories. It is shown that both problems are NP-complete even if all edges of the network have lengths equal to 1. Several special cases of the problems are also investigated, some of which are shown to be solvable in polynomial time and some of which are proved to be NP-complete.