Моя проблема - обобщение задачи, решаемой с помощью [алгоритма Блоссом] Эдмондса. Исходная задача состоит в следующем: для полного графа с взвешенными неориентированными ребрами найти набор ребер такой, что
1) каждая вершина графа смежна только с одним ребром из этого набора (т. Е. Вершины сгруппированы в пары)
2) сумма весов ребер в этом наборе минимальна.
Теперь я хотел бы изменить первую цель в
1 ') вершины сгруппированы в наборы из 3 вершин (или вообще d вершин) и оставляют условие 2) без изменений.
Мои вопросы:
Знаете ли вы, есть ли у этой «обобщенной» проблемы имя?
Знаете ли вы об алгоритме, решающем его по числу шагов, являющихся полиномом от числа вершин (например, алгоритм Блоссома для исходной задачи)? Я не вижу прямого обобщения алгоритма Блоссом, поскольку он основан на поиске путей расширения на графе, сжатом в двудольный граф (и использует здесь венгерский алгоритм). Но увеличивающиеся пути, кажется, не указывают на группы вершин, отличных от пар.
С наилучшими пожеланиями,
Павел