期刊文献+

2-重心问题及其反问题的研究

Studies on the 2-median Problem and Its Inverse Problem on a Tree
下载PDF
导出
摘要 通过研究树上的具有非负权重的2-重心问题,得出了下面的结论:若顶点子集a,b V是树的2-重心,在树上连接顶点a和顶点b有唯一的一条路,去掉路的中点所在的边,树分成两个子树,则a和b分别是所在子树的1-重心.根据这个结论,提出了具体的算法,即树上的具有非负权重的2-重心可以通过在其子树上求1-重心来得到。树上的具有非负权重的2-重心问题的反问题,可以转化为线性规划模型求解,存在有效算法。 Based on the studies of the 2-median problem on a tree with non-negative weights, it is concluded that if the subset {a,b}lohtain in V is the 2 median of the tree, there exists an unique path in the tree joining vertex a with vertex b. Through deleting the edge on which the midpoint of the path lies, the tree is divided into two subtrees, then a and b are the 1-median of the two subtrees respectively. Based on this conclusion, a specific algorithm is proposed to solve the 2-median of the tree with non-negative weights; The inverse 2-meidan problem on a tree with non-negative weights can be translated into "a" linear programming model, which could be solved by an effective algorithm.
出处 《青岛大学学报(自然科学版)》 CAS 2008年第4期34-38,共5页 Journal of Qingdao University(Natural Science Edition)
关键词 选址问题 2-重心问题 p-重心问题的反问题 Location problem 2 - median problem inverse p-median problem
  • 相关文献

参考文献8

  • 1Hakimi S L. Optimal location of switching centers and the absolute centers and medians of a graph [J]. Operations Research, 1964, 12: 450-459.
  • 2Kariv O, Hakimi S L. An algorithmic approach to network location problems [J]. Part Ⅱ:The p-medians, SIAM J. Appl. Math,1979, 37: 539-560.
  • 3Burkard R E, Pleschiutschning C, Zhang Jianzhong. Inverse median problems [J]. Journal of Discrete Optimization, 2004, 1:23 -39.
  • 4Burkard R E, Cela E, Dollani H. 2 median in trees with pos/neg weights [J].Discrete Applied Mathematics, 2000, 105: 51-71.
  • 5Hua. Applications of mathematical models to wheat harvesting [J]. Acta Mathematica Sinica , 1961, 11:63 75 (in Chinese).
  • 6Goldman A J. Optimal center location in simple networks [J].Transportation Science, 1962, 2:77-91.
  • 7Tamir A. An O(pn^2 )algorithm for the p-median and related problems on tree graphs [J]. Operations Ressearch Letters, 1996, 19:59-64.
  • 8Bondy J A, Murty U S R. Graph Theory with Applications [M]. Department of Combinatorics and Optimization, 1976.

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部