Solving NP-Hard Problems on Graphs That Are Almost Trees and an Application to Facility Location Problems

A general technique is described for solving certain NP-hard graph problems in time that is exponential in a parameter k defined as the maximum, over all nonseparable components C of the graph, of the number of edges that must be added to a tree to produce C; for a connected graph, k is no more than the number of edges of the graph minus the number of vertices plus one.The technique is illustrated in detail for the following facility location problem: Given a connected graph G(V, E) such that each edge has an associated positive integer length and given a positive integer r, place the minimum number of centers on points of the graph such that every point of the graph is within distance r from some center (a "point" is either a vertex or a point on some edge).An algorithm of time complexity O(I El. (6r) rkm) is given.A parallel implementation of the algorithm, with optimal speedup over the sequential version for a fairly wide range for the number of processors, is presented.