algorithm - 有向无环图中的最大权连通子图

Question

我正在研究涉及逻辑电路(可以表示为 DAG)的研究问题。 DAG 中的每个节点都有一个给定的权重，可以是负数。我的目标是找到一个连接的子图，使得节点权重的总和最大。

给定边权重的最大权重连通子图问题显然是 NP-hard 问题，但我希望的是定向非循环性质以及我处理节点权重而不是边权重的事实使问题更容易一些。有人可以指出如何开始解决这个问题的正确方向吗？

谢谢

Answer 1

你提到的问题是NP-hard，见:“发现分子相互作用网络中的调节和信号通路”作者:Trey Ideker、Owen Ozier、Benno Schwikowski 和 Andrew F. Siegel，生物信息学，第 18 卷，第 233-240 页，2002

以及本文的补充信息: http://prosecco.ucsd.edu/ISMB2002/nph.pdf