On the computational complexity of the Steiner k-eccentricity

arXiv2112.01140MaRDI QIDQ6384635FDOQ6384635

Guihai Yu, Aleksandar Ilić, Xingfu Li, Sandi Klavžar

Publication date: 2 December 2021

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^{u(G)+1}(n(G)+m(G)+k))$ algorithm is designed, where $u(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].

This page was built for publication: On the computational complexity of the Steiner $k$-eccentricity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6384635)