×

Steiner intervals in strongly chordal graphs. (English) Zbl 1176.05025

Summary: 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.

MSC:

05C12 Distance in graphs
05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite