Upgrading trees under diameter and budget constraints
Given a tree T = (V, E) endowed with a length function I and a cost function c, the diameter lowering problem consists in finding the reals 0 less than or equal to x(e) less than or equal to /(e), e is an element of E such that the tree obtained from T by decreasing the length of every edge e by x(e) units has a minimal diameter subject to the constraint Sigma(Thetais an element ofE)c(e)x(e) less than or equal to B, where B is the available budget (analogously, one can minimize the cost of lowering subject to a diameter constraint). We present an O(\V\(2)) algorithm for solving this problem by developing and using algorithms of similar complexity for related eccentricity lowering problems. (C) 2002 Wiley Periodicals, Inc.
trees diameter network design network upgrade cuts facility location problems