中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 系统科学研究所
The partial inverse minimum spanning tree problem when weight increase is forbidden

文献类型：期刊论文

作者Cai, Mao-Cheng2; Duin, C. W.3; Yang, Xiaoguang2; Zhang, Jianzhong1
刊名EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
出版日期2008-07-16
卷号188期号:2页码:348-353
关键词partial inverse problem spanning tree weight reduction polynomial time algorithms
ISSN号0377-2217
DOI10.1016/j.ejor.2007.04.031
英文摘要In a partial inverse optimization problem there is an underlying optimization problem with a partially given solution. The objective is to find a minimal perturbation of some of the problem's parameter values, in such a way that the partial solution becomes a part of the optimal solution. We consider the partial inverse minimum spanning tree problem in an undirected weighted graph under the constraint that edge weights can not be increased: by decreasing one or more edge weights as little as possible, a given forest must be presented in the new minimum spanning tree. Under a quite general criterion function, evaluating the proposed decreases of weight, we show that this problem can be solved in polynomial time. (c) 2007 Elsevier B.V. All rights reserved.
WOS研究方向Business & Economics ; Operations Research & Management Science
语种英语
WOS记录号WOS:000253183500004
出版者ELSEVIER SCIENCE BV
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/5948]  
专题系统科学研究所
通讯作者Zhang, Jianzhong
作者单位1.Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Hong Kong, Hong Kong, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100080, Peoples R China
3.Univ Amsterdam, Fac Econ & Econometr, Dept Operat Res, NL-1012 WX Amsterdam, Netherlands
推荐引用方式
GB/T 7714		 Cai, Mao-Cheng,Duin, C. W.,Yang, Xiaoguang,et al. The partial inverse minimum spanning tree problem when weight increase is forbidden[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH,2008,188(2):348-353.
APA Cai, Mao-Cheng,Duin, C. W.,Yang, Xiaoguang,&Zhang, Jianzhong.(2008).The partial inverse minimum spanning tree problem when weight increase is forbidden.EUROPEAN JOURNAL OF OPERATIONAL RESEARCH,188(2),348-353.
MLA Cai, Mao-Cheng,et al."The partial inverse minimum spanning tree problem when weight increase is forbidden".EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 188.2(2008):348-353.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。