caa a22 4500 445805358 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-009-9377-1 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9377-1 Babenko Maxim Dept. of Mechanics and Mathematics, Moscow State University, Yandex LLC, Russia aut An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem [Elektronische Daten] [Maxim Babenko] Let G=(VG,AG) be a digraph and let S ⊔ T be a bipartition of VG. Abibranching is a subsetB⊆AG such that for each node s∈S there exists a directed s-T path inB and, vice versa, for each node t∈T there exists a directed S-t path 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 in O(n′(m+nlog n)) time (where n:=|VG|, m:=|AG|, n′:=min (|S|,|T|)). Assuming that arc weights are integers we develop a weight-scaling algorithm of time complexity $O(m\sqrt{n}\;\log n\log(nW))$ for the minimum weight bibranching problem (where W denotes the maximum magnitude of arc weights). Springer Science+Business Media, LLC, 2009 Branching nationallicence Bipartite edge cover nationallicence Weight scaling nationallicence Primal-dual algorithm nationallicence Blocking augmentation nationallicence Algorithmica Springer-Verlag 61/4(2011-12-01), 898-922 0178-4617 61:4<898 2011 61 453 https://doi.org/10.1007/s00453-009-9377-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9377-1 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Babenko Maxim Dept. of Mechanics and Mathematics, Moscow State University, Yandex LLC, Russia aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 898-922 0178-4617 61:4<898 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer