Czy ktoś z was ma namiary na opis algorytmów aproksymacyjnych rozwiązujących uogólniony problem drzewa Steinera (GSTP) ?
Dla sprecyzowania:
Dany jest graf nieskierowany z krawędziami o wagach nieujemnych G=<V,E>. Zbiór wierzchołków V jest podzielony na dwa podzbiory: wierzchołki wymagane W i wierzchołki Steinera S. Należy znaleźć minimalne drzewo rozpinające zawierające wszystkie wierzchołki wymagane i dowolny podzbiór wierzchołków Steinera.
W sieci jest sporo na ten temat, ale wszystkie rozwiązania ograniczają się albo do grafów pełnych, albo są to szczególne wersje tego problemu (np. metryczny).