Improved Algorithms for Computing k-Sink on Dynamic Flow Path Networks
| Autor: | Tsunehiko Kameda, Yuya Higashikawa, Binay K. Bhattacharya, Mordecai J. Golin, Naoki Katoh |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Efficient algorithm
0102 computer and information sciences 02 engineering and technology Binary logarithm 01 natural sciences Flow (mathematics) 010201 computation theory & mathematics Path (graph theory) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Completion time Sink (computing) Algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783319621265 WADS |
| DOI: | 10.1007/978-3-319-62127-2_12 |
| Popis: | We address the problem of locating k sinks on dynamic flow path networks with n vertices in such a way that the evacuation completion time to them is minimized. Our two algorithms run in \(O(n\log n + k^2\log ^4 n)\) and \(O(n\log ^3 n)\) time, respectively. When all edges have the same capacity, we also present two algorithms which run in \(O(n + k^2\log ^2n)\) time and \(O(n\log n)\) time, respectively. These algorithms together improve upon the previously most efficient algorithms, which have time complexities \(O(kn\log ^2n)\) [1] and O(kn) [11], in the general and uniform edge capacity cases, respectively. The above results are achieved by organizing relevant data for subpaths in a strategic way during preprocessing, and the final results are obtained by extracting/merging them in an efficient manner. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|