一个图的算法问题。大虾给出个算法来
有n个结点组成一个有向无环图,这n个结点中有m <=n个特殊结点,如何把这个有向无环图分解成多个有向无环图,每个子有向无环图最多包含k个特殊结点?有最优算法吗?
现在我猜分解出(m mod k)+1 个子DAG就满足了,但是不知道怎么求解。
[解决办法]
每个node都成一个DAG不就行了。你是不是要最小化subgraph的数目?
发布时间: 2012-02-16 21:30:36 作者: rapoo
一个图的算法问题。大虾给出个算法来
有n个结点组成一个有向无环图,这n个结点中有m <=n个特殊结点,如何把这个有向无环图分解成多个有向无环图,每个子有向无环图最多包含k个特殊结点?有最优算法吗?
现在我猜分解出(m mod k)+1 个子DAG就满足了,但是不知道怎么求解。
[解决办法]
每个node都成一个DAG不就行了。你是不是要最小化subgraph的数目?