Steiner Intervals in Strongly Chordal Graphs.

Abstract

A Steiner tree for a set $S$ of vertices in a connected graph $G$ is a connected subgraph of $G$ of smallest size that contains $S$. The Steiner interval $I(S)$ of $S$ is the union of all vertices of $G$ that belong to some Steiner tree for $S$. A graph is strongly chordal if it is chordal and has the property that every even cycle of length at least six has an odd chord. We develop an efficient algorithm for finding Steiner intervals of sets of vertices in strongly chordal graphs.