19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors