Optimal location of a path or tree on a network with cycles

Abstract

Abstract This paper concerns the problem of locating a path‐ or tree‐shaped facility on a network. For median and center, min and max problems, we consider on which classes of networks the optimal facility location can be found in polynomial time. Some of these problems can be solved on series‐parallel graphs, but by high‐order polynomial‐ or pseudo‐polynomial‐time algorithms. Many of the problems that use pseudo‐polynomial time are shown to be NP‐complete on outerplanar graphs, a subset of series‐parallel graphs.