کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421481 | 684491 | 2006 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An O(nlog2n) algorithm for the optimal sink location problem in dynamic tree networks An O(nlog2n) algorithm for the optimal sink location problem in dynamic tree networks](/preview/png/421481.png)
In this paper, we consider a sink location in a dynamic network which consists of a graph with capacities and transit times on its arcs. Given a dynamic network with initial supplies at vertices, the problem is to find a vertex vv as a sink in the network such that we can send all the initial supplies to vv as quickly as possible. We present an O(nlog2n) time algorithm for the sink location problem, in a dynamic network of tree structure where n is the number of vertices in the network. This improves upon the existing O(n2)O(n2)-time bound [S. Mamada, K. Makino, S. Fujishige, Optimal sink location problem for dynamic flows in a tree network, IEICE Trans. Fundamentals E85-A (2002) 1020–1025]. As a corollary, we also show that the quickest transshipment problem can be solved in O(nlog2n) time if a given network is a tree and has a single sink. Our results are based on data structures for representing tables (i.e., sets of intervals with their height), which may be of independent interest.
Journal: Discrete Applied Mathematics - Volume 154, Issue 16, 1 November 2006, Pages 2387–2401