The partial inverse minimum spanning tree problem when weight increase is forbidden

doi:10.1016/j.ejor.2007.04.031

CSpace > 系统科学研究所

	The partial inverse minimum spanning tree problem when weight increase is forbidden
	Cai, Mao-Cheng 2; Duin, C. W.3; Yang, Xiaoguang2 ; Zhang, Jianzhong 1
	2008-07-16
发表期刊	EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
ISSN	0377-2217
卷号	188 期号:2 页码:348-353
摘要	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.
关键词	partial inverse problem spanning tree weight reduction polynomial time algorithms
DOI	10.1016/j.ejor.2007.04.031
语种	英语
WOS研究方向	Business & Economics ; Operations Research & Management Science
WOS类目	Management ; Operations Research & Management Science
WOS记录号	WOS:000253183500004
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/5949
专题	系统科学研究所
通讯作者	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.