Algorytm największych zbiorów niezależnych

0

Witam potrzebuję następującego algorytmu:
Dany jest graf G=(V,E). Podzbiór ScV nazywamy niezależnym gdy dla dowolnych u,c S, uv1, (u, v)E. Podać algorytm wyznaczający maksymalny podzbiór wierzchołków niezależnych w drzewie .

1

zamiast kombinować z własna niezrozumiałą definicją trzeba było dać link do wiki: http://pl.wikipedia.org/wiki/Zbi%C3%B3r_niezale%C5%BCny albo ją zacytować.

1

@autor http://pl.wikipedia.org/wiki/Problem_zbioru_niezależnego
http://en.wikipedia.org/wiki/Independent_set_problem
Problem jest NP-zupełny więc nic poniżej wykładniczej złożoności tu nie wyciśniesz.

1 użytkowników online, w tym zalogowanych: 0, gości: 1