Name
Abstract | ||
|---|---|---|
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(2) n) 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(2) n) [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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-62127-2_12 | ALGORITHMS AND DATA STRUCTURES: 15TH INTERNATIONAL SYMPOSIUM, WADS 2017 |
Field | DocType | Volume |
Binary logarithm,Discrete mathematics,Combinatorics,Vertex (geometry),Algorithm,Mathematics,Sink (computing) | Conference | 10389 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
6 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Binay K. Bhattacharya | 1 | 332 | 49.20 |
| Mordecai J. Golin | 2 | 0 | 0.34 |
| Yuya Higashikawa | 3 | 64 | 12.71 |
| Tsunehiko Kameda | 4 | 282 | 35.33 |
| naoki katoh | 5 | 1101 | 187.43 |