16.05.2011 9:00 Seminarska soba v Galebu

Lecturer: dr. Matjaž Kovše ( FNM, Univerza v Mariboru and IMFM, Ljubljana )

 

Title: Steiner index of a graph
Abstract: 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 sG(H). It is well known that for k3, it is generally NP-hard to compute sG(H). The k-th Steiner index of a graph G is defined as the sum of all values sG(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.