10.3969/j.issn.1000-3428.2011.07.092
网络1-重心反问题的计算复杂性研究
在网络中顶点的权值可以改变的情况下,对哈明距离下以及l1模下1-重心问题的反问题进行研究.通过将哈明距离下网络1-重心问题的反问题归约为0-1背包问题,证明即使是在链式网络中,在哈明距离下该问题仍是NP困难的,并给出l1模下在一般网络中求解1-重心反问题的多项式时间算法.
1-重心、哈明距离、l1模、反问题、NP困难
37
TP301.6(计算技术、计算机技术)
国家自然科学基金重大计划资助项目90818020;国家自然科学基金资助项目10601051;浙江省自然科学基金资助项目Y6090472;浙江省教育厅科研基金资助项目Y201018835
2011-07-08(万方平台首次上网日期,不代表论文的发表时间)
共3页
274-275,278