文章基本信息

标题：Finding minimal branchings with a given number of arcs
本地全文：下载
作者：Cvetković Dragoš M. ; Čangalović Mirjana M.
期刊名称：Yugoslav Journal of Operations Research
印刷版ISSN：0354-0243
电子版ISSN：1820-743X
出版年度：2002
卷号：12
期号：1
页码：1-10
DOI：10.2298/YJOR0201001C
出版社：Faculty of Organizational Sciences, Belgrade, Mihajlo Pupin Institute, Belgrade, Economics Institute, Belgrade, Faculty of Transport and Traffic Engineering, Belgrade, Faculty of Mechanical Engineering, Belgrade
摘要：
We describe an algorithm for finding a minimal s-branching (where s is a given number of its arcs) in a weighted digraph with an a symetric weight matrix. The algorithm uses the basic principles of the method (previously developed by J. Edmonds) for determining a minimal branching in the case when the number of its arcs is not specified in advance. Here we give a proof of the correctness for the described algorithm.
关键词：Combinatorial optimization; weighted graphs; minimal branching.