ON LOCATING A SINGLE PATH-LIKE FACILITY IN A GENERAL GRAPH

The problem of locating a path-like facility of fixed length Lr a tree can be solved in polynomial time. However, this problem is NP-complet e evert on very sparse graphs such as outerplanar graphs. We shore tha t if the length of the facility to be located is small then the corres ponding path location problem can be solved efficiently; We suggest O (n(4) log n) and O (n(4)) algorithms to solve the problem of locating small paths with minmax and minsum criteria oil a general graph: We al so give a method to solve small path location problems with a geneal n onlinear objective function. If the path-like facility to be located i s known to be contained in some path with at most r nodes then we show that, for fixed r, the path location problem is solvable in polynomia l time.