An <i>O</i>(<i>kn</i>)-Time Algorithm to Solve Steiner (<i>k</i>, <i>k</i>′)-Eccentricity on Trees

Abstract

Steiner (k,k′)-eccentricity on a given fixed k′-subset in a graph G is the maximum Steiner distance over all k-subsets of V(G) which contain the fixed k′-set, where the Steiner distance of a set is the size of a minimum Steiner tree on this set in a graph. Let R⊆V(T) be the given fixed k′-subset in a tree T. Let k1 and k2 be two integers such that k1≥k2≥k′. We prove that, in a tree, every optimal solution of Steiner (k1,k′)-eccentricity on R takes some optimal solution of Steiner (k2,k′)-eccentricity on R as a partial solution. On the other hand, every optimal solution of Steiner (k2,k′)-eccentricity on R is part of some optimal solution of Steiner (k1,k′)-eccentricity on the set R in a tree. Finally, we present an O(kn)-time algorithm to solve Steiner (k,k′)-eccentricity on a given fixed k′-set in trees.

Keywords

• Steiner eccentricity
• algorithm
• tree