An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem
复制标题
最小权分枝问题的高效缩放算法
DOI：
10.1007/s00453-009-9377-1
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
M. Babenko
中科院分区：
文献类型：
--
作者：
M. Babenko
设G =（VG，AG）是一个有向图，S_（？）T是VG的一个双划分. Abibranching是一个子集B ∈ AG，使得对于每个节点∈ S，存在B中的有向T路，反之亦然，对于每个节点∈ T，存在B中的有向S-t路. KeijandPendavingh提出了一个强多项式原始-对偶算法，该算法在O（n′（m+nlogn））时间内找到一个最小权双分支（其中n：|VG|，m：=| AG|，n′：=min（|S|,|不|假设弧权为整数，我们对最小权双分支问题（其中W表示弧权的最大值）提出了一个时间复杂度为权标度的算法。
LetG=(VG,AG) be a digraph and letS⊔Tbe a bipartition ofVG. Abibranchingis a subsetB⊆AGsuch that for each nodes∈Sthere exists a directeds–Tpath inBand, vice versa, for each nodet∈Tthere exists a directedS–tpath inB.Bibranchings generalize both branchings and bipartite edge covers. Keijsper and Pendavingh proposed a strongly polynomial primal-dual algorithm that finds a minimum weight bibranching inO(n′(m+nlogn)) time (wheren:=|VG|,m:=|AG|,n′:=min (|S|,|T|)).Assuming that arc weights are integers we develop a weight-scaling algorithm of time complexityfor the minimum weight bibranching problem (whereWdenotes the maximum magnitude of arc weights).