Record number :
885949
Title of article :
An improved algorithm for the k-source maximum eccentricity spanning trees Original Research Article
Author/Authors :
Bang Ye Wu، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Pages :
9
From page :
342
To page :
350
Abstract :
Let G=(V,E,w) be an undirected graph with positive edge lengths and S⊂V a set of k specified sources. The k-source maximum eccentricity spanning tree is a spanning tree T minimizing the maximum distance from a source to a vertex, i.e., maxs∈S {maxv∈V{dT(s,v)}}, where dT(s,v) is the length of the path between s and v in T. In this paper, we propose an O(|V|2 log |V|+|V| |E|) time algorithm, which improves the previous result on the problem.
Keywords :
optimization problems , Algorithms , Network design , Spanning trees
Journal title :
Discrete Applied Mathematics
Serial Year :
2004
Link To Document :
بازگشت