使用三元树查找最小顶点覆盖

Question

我找到了一些算法来找到最小顶点覆盖，就像使用二叉搜索树一样，但我读到使用三叉树更好。但我找不到任何关于它的信息，也想不出它的算法

有人知道怎么做吗？

Answer 1

给定一个图，选择任意边uv作为枢轴。三元搜索树的三个分支是：(1(我们取u但不取v(2(我们取v但不取u(3(我们同时取u和v。在情况(1(中，我们被迫取v的邻居，在情况(2(中，被迫取u的邻居。若要构造子问题，请删除所获取的顶点及其入射边。