На самом деле я работаю с невзвешенными неориентированными графами. Я ищу алгоритмы, эффективные при исследовании наименьшего возможного подмножества узлов исходного графа, которое касается всех остальных узлов (или содержит их). В клике любой узел будет лучшим решением.
На этом графике: было бы множество решений, таких как [1,4], [4,5], [2,6] и т. д. Это очень напоминает мне проблема минимального покрытия вершин, но я ничего не могу найти о покрытии узлов. У него есть конкретное название? Является ли это распространенным вариантом минимального вершинного покрытия?