送交者: 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