Inverse problem of minimum cuts

	Inverse problem of minimum cuts
	Zhang, JZ ; Cai, MC
刊名	MATHEMATICAL METHODS OF OPERATIONS RESEARCH
	1998
卷号	47 期号:1 页码:51-58
关键词	inverse problem maximum flow minimum cut minimum cost circulation strongly polynomial algorithm
ISSN号	1432-2994
英文摘要	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.
WOS研究方向	Operations Research & Management Science ; Mathematics
语种	英语
出版者	PHYSICA VERLAG GMBH
WOS记录号	WOS:000073097700003
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/13370]
专题	中国科学院数学与系统科学研究院
通讯作者	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.