Steiner-Baum-Problem

Das Steiner-Baum-Problem in der Informatik und Graphentheorie ist das Problem, einen minimalen Teilgraphen eines ungerichteten Graphen zu finden, der eine gegebene Menge von Terminalknoten verbindet. Das Ziel besteht darin, das gesamte Gewicht aller Kanten im Teilgraphen zu minimieren. Dieses Problem ist NP-schwer, was bedeutet, dass die Berechnung einer optimalen Lösung eine hohe rechnerische Komplexität hat. Das Steiner-Baum-Problem hat erhebliche Anwendungen in Bereichen wie der Kommunikationsnetzwerkplanung und der Layoutoptimierung integrierter Schaltkreise.