Abstract
Let G = (VG, AG) be a digraph and let \(S \sqcup T\) be a bipartition of VG. A bibranching is a subset B ⊆ AG such that for each node s ∈ S there exists a directed s–T path in B and, vice versa, for each node t ∈ T there exists a directed S–t path in B.
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 + n logn)) time (where , , ).
In this paper we develop a weight-scaling \(O(m \sqrt{n} \; \log n \log(nW))\)-time algorithm for the minimum weight bibranching problem (where W denotes the maximum magnitude of arc weights).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Dinic, E.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277–1280 (1980)
Edmonds, J.: Optimum branchings. J. Res. Nat. Bur. Standards 71B, 233–240 (1967)
Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Gabow, H., Galil, Z., Spencer, T., Tarjan, R.: Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6(2), 109–122 (1986)
Goldberg, A., Tarjan, R.: Solving minimum-cost flow problems by successive approximation. In: STOC 1987: Proceedings of the nineteenth annual ACM conference on Theory of computing, pp. 7–18 (1987)
Gabow, H., Tarjan, R.: Faster scaling algorithms for network problems. SIAM J. Comput. 18(5), 1013–1036 (1989)
Gablow, H., Tarjan, R.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815–853 (1991)
Keijsper, J., Pendavingh, R.: An efficient algorithm for minimum-weight bibranching. J. Comb. Theory, Ser. B 73(2), 130–145 (1998)
Schrijver, A.: Min-max relations for directed graphs. Ann. Discrete Math. 16, 261–280 (1982)
Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)
Sleator, D., Tarjan, R.: A data structure for dynamic trees. Journal of Computer and System Sciences 26(3), 362–391 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Babenko, M.A. (2008). An Efficient Scaling Algorithm for the Minimum Weight Bibranching Problem. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)