Inverse problem of minimum cuts

CSpace

	Inverse problem of minimum cuts
	Zhang, JZ ; Cai, MC
	1998
发表期刊	MATHEMATICAL METHODS OF OPERATIONS RESEARCH
ISSN	1432-2994
卷号	47 期号:1 页码:51-58
摘要	Given a network N = (V,A, c), a source s is an element of V, a sink t is an element of V and some s - t cuts and suppose each element of the capacity vector c can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all those s - t cuts become minimum cuts with respect to the new capacities. In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.
关键词	inverse problem maximum flow minimum cut minimum cost circulation strongly polynomial algorithm
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000073097700003
出版者	PHYSICA VERLAG GMBH
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/13371
专题	中国科学院数学与系统科学研究院
通讯作者	Zhang, JZ
作者单位	1.Chinese Univ Hong Kong, Dept Math, Hong Kong, Hong Kong 2.Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Zhang, JZ,Cai, MC. Inverse problem of minimum cuts[J]. MATHEMATICAL METHODS OF OPERATIONS RESEARCH,1998,47(1):51-58.
APA	Zhang, JZ,&Cai, MC.(1998).Inverse problem of minimum cuts.MATHEMATICAL METHODS OF OPERATIONS RESEARCH,47(1),51-58.
MLA	Zhang, JZ,et al."Inverse problem of minimum cuts".MATHEMATICAL METHODS OF OPERATIONS RESEARCH 47.1(1998):51-58.