graph - 完整图中“广义”匹配的算法

Question

我的问题是 Edmonds [Blossom algorithm] 解决的任务的概括。最初的任务如下：给定一个带有加权无向边的完整图，找到一组边，使得

1) 图中的每个顶点仅与该集合中的一条边相邻（即顶点被分组为对）

2）该集合中边的权重之和最小。

现在，我想将第一个目标修改为 1') 顶点被分组为 3 个顶点（或通常为 d 个顶点）的集合，并保持条件 2) 不变。

我的问题：

1. 你知道这个“广义”问题是否有名字吗？

2. 你知道一个算法解决它的步骤数是顶点数的多项式（如原始问题的 Blossom 算法）？我没有看到 Blossom 算法的简单概括，因为它基于在压缩为二分图的图上寻找增强路径（并在此处使用匈牙利算法）。但增广路径似乎并不指向不同于对的顶点组。

最好的问候， Paweł

标签： graphmatchingperfect