请教:如何证明一个关于graph traversal的NP-Complete问题



所有跟贴·加跟贴·新语丝科技论坛

送交者: xm1223 于 2005-12-29, 15:15:52:

在研究中(distributed computing),引出了一个关于graph traversal的optimal问题(类似于Layout问题中的Bandwidth,但是邻接点必须有边连(遍历嘛),允许节点被多次访问), 需要证明该问题是NP-Complete(我和导师都认为是NP-complete问题),然后设计些heuristic算法来找接近最优的遍历。感觉上应该能证明,但我对NP-Complete证明和graph theory都不熟悉,无从下手。希望哪位朋友能帮忙指点一下,如果有合适的结果, 也可以一起发表论文。 谢谢。

我的email: xm1223@yahoo.com




所有跟贴:


加跟贴

笔名: 密码(可选项): 注册笔名请按这里

标题:

内容(可选项):

URL(可选项):
URL标题(可选项):
图像(可选项):


所有跟贴·加跟贴·新语丝科技论坛