У меня есть невзвешенный, связанный граф. Я хочу найти подключенный подграф, который определенно включает в себя определенный набор узлов и как можно меньше дополнений. Как это можно сделать?
На всякий случай, я повторю вопрос, используя более точный язык. Пусть G (V, E) - невзвешенный, неориентированный, связный граф. Пусть N - некоторое подмножество V. Какой наилучший способ найти наименьший связный подграф G '(V', E ') группы G (V, E) такой, что N является подмножеством V'?
Аппроксимации прекрасны.