алгоритм «обобщенного» сопоставления в полных графах - PullRequest
0 голосов
/ 04 июля 2018

Моя проблема - обобщение задачи, решаемой с помощью [алгоритма Блоссом] Эдмондса. Исходная задача состоит в следующем: для полного графа с взвешенными неориентированными ребрами найти набор ребер такой, что

1) каждая вершина графа смежна только с одним ребром из этого набора (т. Е. Вершины сгруппированы в пары)

2) сумма весов ребер в этом наборе минимальна.

Теперь я хотел бы изменить первую цель в 1 ') вершины сгруппированы в наборы из 3 вершин (или вообще d вершин) и оставляют условие 2) без изменений.

Мои вопросы:

  1. Знаете ли вы, есть ли у этой «обобщенной» проблемы имя?

  2. Знаете ли вы об алгоритме, решающем его по числу шагов, являющихся полиномом от числа вершин (например, алгоритм Блоссома для исходной задачи)? Я не вижу прямого обобщения алгоритма Блоссом, поскольку он основан на поиске путей расширения на графе, сжатом в двудольный граф (и использует здесь венгерский алгоритм). Но увеличивающиеся пути, кажется, не указывают на группы вершин, отличных от пар.

С наилучшими пожеланиями, Павел

...