A strongly polynomial algorithm for the inverse shortest arborescence problem

CSpace

	A strongly polynomial algorithm for the inverse shortest arborescence problem
	Hu, ZQ ; Liu, ZH
	1998-03-02
发表期刊	DISCRETE APPLIED MATHEMATICS
ISSN	0166-218X
卷号	82 期号:1-3 页码:135-154
摘要	In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given upsilon(1)-arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n(3)) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem. (C) 1998 Elsevier Science B.V. All rights reserved.
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000072847400009
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13785
专题	中国科学院数学与系统科学研究院
通讯作者	Hu, ZQ
作者单位	1.Cent China Normal Univ, Dept Math, Wuhan 430079, Peoples R China 2.Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Hu, ZQ,Liu, ZH. A strongly polynomial algorithm for the inverse shortest arborescence problem[J]. DISCRETE APPLIED MATHEMATICS,1998,82(1-3):135-154.
APA	Hu, ZQ,&Liu, ZH.(1998).A strongly polynomial algorithm for the inverse shortest arborescence problem.DISCRETE APPLIED MATHEMATICS,82(1-3),135-154.
MLA	Hu, ZQ,et al."A strongly polynomial algorithm for the inverse shortest arborescence problem".DISCRETE APPLIED MATHEMATICS 82.1-3(1998):135-154.