さて、各頂点 v で値 N(v) と M(v) を持つルート付きツリーが与えられます。ここで、N(v) はサブツリー Tv の最小サイズの頂点カバーの値です。ノード、M(v) は部分木 Tv の最小サイズの頂点カバーの値です。
私が正しく理解していれば、これはルートノードが実際にツリー T の最小サイズの頂点を含むことを意味します (ルートノードのサブツリーはツリー自体であるため)。したがって、これは、ツリーの最小サイズの頂点カバーがどのくらいの大きさになるかを知っていることを意味します。
最高度の頂点を選択し、そのノードに隣接するエッジとノードをツリーから削除し、エッジがなくなるまでこの方法を続けるという貪欲なアプローチを使用することを考えていました。N(v) と M(v) が何であるかを知っていることを考えると、これは線形時間アルゴリズムになりますか?