текущие потоки графического процессора как-то ограничены (ограничение памяти, ограничение структуры данных, отсутствие рекурсии...).
Как вы думаете, было бы возможно реализовать проблему теории графов на GPU. например, крышка верхушки? доминирующий набор? независимый набор? max clique?....
Можно ли также иметь алгоритмы с ветвями и границами на графических процессорах? Рекурсивный откат?
Вас будет интересовать
Это касательно связано с вашим вопросом, но я реализовал "рекурсивный" алгоритм обратного отслеживания для перечисления "самоуничтожающихся прогулок" на решетке (nb: стек был смоделирован в ядре CUDA, чтобы избежать накладных расходов создание локальных переменных для целой группы вызовов функций). Это можно сделать эффективно, поэтому я уверен, что это можно адаптировать к теоретическому контексту графика. Вот ссылка на семинар по теме, где я дал общее обсуждение вопроса о возврате в рамках парадигмы множественных данных Single Instruction Multiple Data (SIMD); это pdf размером около 1 МБ http://bit.ly/9ForGS.
Я не утверждаю, что знаю о более широкой литературе по графическим теоретическим алгоритмам на графических процессорах, но надеюсь, что это поможет немного.
(@TheMachineCharmer, спасибо за ссылки.)