Simple linear flow decomposition algorithms on trees, circles, and augmented trees. (English) Zbl 1269.90136
Summary: The flow decomposition algorithm transforms an arc flow-based solution to a network flow problem into flows on directed paths and cycles. When the undirected graph induced by arcs with positive flow is a tree, a circle, or an augmented tree (with \(n\) nodes), the standard implementation of the algorithm runs in \(O(n^{2})\) time. In this article, we exploit the structure of the network to develop an \(O (n)\) flow decomposition algorithm. The run-time relies on the property that for these networks, paths or cycles can be represented implicitly in \(O (1)\) space. The algorithm is easy to implement and does not use complicated data structures. Because the size of the input is \(O (n)\), our algorithm is the fastest possible for flow decomposition on these special networks. Our algorithm can be used to improve run-times for solving matching and transportation problems on trees and circles.
MSC:
| 90C35 | Programming involving graphs or networks |
| 05C90 | Applications of graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
Keywords:
network flow algorithms; flow decomposition; complexity analysis; trees; circles; augmented treesReferences:
| [1] | Ahuja, Network flows: Theory, algorithms, and applications (1993) · Zbl 1201.90001 |
| [2] | Vaidyanathan, Fast algorithms for specially structured minimum cost flow problems with applications, Oper Res 58 pp 1681– (2010) · Zbl 1231.90111 · doi:10.1287/opre.1100.0846 |
| [3] | Orlin, Fast algorithms for convex cost flow problems on circles, lines, and trees (2012) · Zbl 1338.05109 |
| [4] | Toussaint, A comparison of rhythmic similarity measures, Technical report SOCS-TR-2004.6 (2004) |
| [5] | J. M. Diaz-Banez G. Farigu F. Gomez D. Rappaport G. T. Toussaint El compas flamenco: A phylogenetic analysis 2004 61 70 |
| [6] | Typke, Using transportation distances for measuring melodic similarity, Technical report uu-cs-2003-024 (2003) |
| [7] | Ben-Dor, The restriction scaffold problem, J Comput Biol 10 pp 385– (2003) · doi:10.1089/10665270360688084 |
| [8] | Colannino, An algorithm for computing the restriction scaffold assignment problem in computational biology, Inf Process Lett 95 pp 466– (2005) · Zbl 1182.68354 · doi:10.1016/j.ipl.2005.05.007 |
| [9] | Colannino, An O(n log n) algorithm for the restriction scaffold assignment problem, J Comput Biol 13 pp 979– (2006) · doi:10.1089/cmb.2006.13.979 |
| [10] | Aggarwal, Efficient minimum cost matching and transportation using the quadrangle inequality, J Algorithms 19 pp 116– (1995) · Zbl 0849.68043 · doi:10.1006/jagm.1995.1030 |
| [11] | Cheng, Distributed computing for a tree network with communication delays, IEEE Trans Aerosp Electron Syst 26 pp 511– (1990) · doi:10.1109/7.106129 |
| [12] | Kim, Optimal load distribution from tree network processors, IEEE Trans Aerosp Electron Syst 32 pp 607– (1996) · doi:10.1109/7.489505 |
| [13] | Bataineh, Bus-oriented load sharing for a network of sensor driven processors, IEEE Trans Syst Man, Cybern 21 pp 1202– (1991) · doi:10.1109/21.120070 |
| [14] | Bokhari, A network flow model for load balancing in circuit-switched multicomputers, IEEE Trans Parallel Dist Syst 4 pp 649– (1993) · doi:10.1109/71.242158 |
| [15] | Sleator, A data structure for dynamic trees, J Comput Syst Sci 26 pp 362– (1983) · Zbl 0509.68058 · doi:10.1016/0022-0000(83)90006-5 |
| [16] | Goldberg, A new approach to the maximum flow problem, J ACM 35 pp 921– (1988) · Zbl 0661.90031 · doi:10.1145/48014.61051 |
| [17] | Ahuja, Improved time bounds for the maximum flow problem, SIAM J Comput 18 pp 939– (1989) · Zbl 0675.90029 · doi:10.1137/0218065 |
| [18] | Tarjan, Dynamic trees as search trees via Euler tours applied to the network simplex algorithm, Math Program 78 pp 169– (1997) · Zbl 0889.90150 · doi:10.1007/BF02614369 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
