Minimax flow tree problems
Hui Chen, Ann Melissa Campbell, Barrett W. Thomas, Arie Tamir · Networks · 2009
Abstract We examine a class of problems that seeks to find tree‐structured networks that minimize the maximum cost among a subset of nodes in a graph. The cost metric is characterized by a series of parameters that can represent distance, flow volume, and delivery deadlines. Derived through variations in problem parameters, we present 17 different problems and discuss their worst‐case complexities. Fourteen of the problems are new to the literature. We show that some of the problems are 𝒩𝒫‐Complete and others are polynomially solvable. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009