Upgrading trees under diameter and budget constraints
Victor D. Chepoi, Hartmut Noltemeier, Yann Vaxès · Networks · 2002
Abstract Given a tree T = (V, E) endowed with a length function l and a cost function c, the diameter lowering problem consists in finding the reals 0 ≤ x(e) ≤ l(e), e ∈ 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 ∑e∈Ec(e)x(e) ≤ 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. © 2002 Wiley Periodical, Inc.