Premium
Simple linear flow decomposition algorithms on trees, circles, and augmented trees
Author(s) -
Vaidyanathan Balachandran
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21470
Subject(s) - algorithm , flow (mathematics) , flow network , maximum flow problem , computer science , simple (philosophy) , decomposition , tree (set theory) , matching (statistics) , time complexity , simple algorithm , multi commodity flow problem , data structure , graph , mathematics , mathematical optimization , theoretical computer science , combinatorics , biology , programming language , thermodynamics , ecology , philosophy , geometry , epistemology , statistics , physics
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. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012