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

Question

我找到了一些算法来找到最小的 Vertex-Cover，比如使用二叉搜索树，但我读到使用三叉树更好。但是我找不到任何关于它的信息或想出它的算法。

有人知道怎么做吗？

Answer 1

给定一个图，选择任意一条边 uv 作为轴心。三元搜索树的三个分支是 (1) 我们取 u 但不取 v (2) 我们取 v 但不取 u (3) 我们同时取 u 和 v。在情况 (1) 中我们被迫取 v邻居，在情况 (2) 中，我们被迫带走你的邻居。要构建子问题，请删除所取的顶点及其关联边。