On the computational complexity of the Steiner $k$-eccentricity

Abstract

The Steiner $k$-eccentricity of a vertex $v$ of a graph $G$ is the maximum Steiner distance over all $k$-subsets of $V(G)$ which contain $v$. A linear time algorithm for calculating the Steiner $k$-eccentricity of a vertex on block graphs is presented. For general graphs, an $O(n^{\nu (G)+1}(n(G)+m(G)+k))$ algorithm is designed, where $\nu (G)$ is the cyclomatic number of $G$. A linear algorithm for computing the Steiner $3$-eccentricities of all vertices of a tree is also presented which improves the quadratic algorithm from [Discrete Appl.\ Math.\ 304 (2021) 181--195].