In this paper, we consider a coverage problem for uncertain points in a tree. Let T be a tree containing a set P of n (weighted) demand points, and the location of each demand point P_i P is uncertain but is known to appear in one of m_i points on T each associated with a probability. Given a covering range , the problem is to find a minimum number of points (called centers) on T to build facilities for serving (or covering) these demand points in the sense that for each uncertain point P_i P, the expected distance from P_i to at least one center is no more than @math . The problem has not been studied before. We present an O(|T|+M ^2 M) time algorithm for the problem, where |T| is the number of vertices of T and M is the total number of locations of all uncertain points of P, i.e., M= P_i P m_i. In addition, by using this algorithm, we solve a k-center problem on T for the uncertain points of P.
As mentioned above, the deterministic'' version of the center-coverage problem is solvable in linear time @cite_19 , where all demand points are on the vertices. For the @math -center problem, Megiddo and Tamir @cite_12 presented an @math time algorithm ( @math is the size of the tree), which was improved to @math time by Cole @cite_21 . The unweighted case was solved in linear time by Frederickson @cite_11 .
@cite_19 @cite_21 @cite_12 @cite_11
2010961994 1671942308 2032624334 1529668588
Problems of finding p-centers and dominating sets of radius r in networks are discussed in this paper. Let n be the number of vertices and @math be the number of edges of a network. With the assumption that the distance-matrix of the network is available, we design an @math algorithm for finding an absolute 1-center of a vertex-weighted network and an @math algorithm for finding an absolute 1-center of a vertex-unweighted network (the problem of finding a vertex 1-center of a network is trivial). We show that the problem of finding a (vertex or absolute) p-center (for @math ) of a (vertex-weighted or vertex-unweighted) network, and the problem of finding a dominating set of radius r are @math -hard even in the case where the network has a simple structure (e.g., a planar graph of maximum vertex degree 3). However, we describe an algorithm of complexity @math (respectively, $ O[| E |^p n^ 2p - 1... Megiddo introduced a technique for using a parallel algorithm for one problem to construct an efficient serial algorithm for a second problem. We give a general method that trims a factor o f 0(logn) time (or more) for many applications of this technique. An @math algorithm for the continuous p-center problem on a tree is presented. Following a sequence of previous algorithms, ours is the first one whose time bound in uniform in p and less than quadratic in n. We also present an @math algorithm for a weighted discrete p-center problem. Linear-time and -space algorithms are presented for solving three versions of the p-center problem in a tree. The techniques are an application of parametric search.