Steiner index of a graph
Presented by Matjaž KOVšE
Type: Oral presentation
Track: Algorithmic Graph Theory
Given a subset $H$ of $k$ vertices in a connected graph $G$ the $k$-Steiner tree problem is that of finding a connected subgraph of $G$, that contains all the $k$ vertices and has the minimum number of edges among all such subgraphs. The number of edges in this subgraph is denoted by $s_G(H)$. It is well known that for $k \geq 3$, it is generally $NP$-hard to compute $s_G(H)$. The $k$-th Steiner index of a graph $G$ is defined as the sum of all values $s_G(H)$, where $H$ ranges over all subsets of $k$ vertices of $G$. For $k=2$ this definition coincides with the definition of well known and well studied Wiener index. Hamming graphs are the Cartesian products of complete graphs, and their isometric subgraphs are called partial Hamming graphs. A polynomial time algorithm for computing the $k$-th Steiner index of partial Hamming graphs will be presented. The main ingredient will be the canonical metric representation of a graph.