| Presentation | 1997/9/18 A Linear Time Dijkstra Algorithm to Determine Fastest File Transfer on a Fixed Route Satoshi ADACHI, Yoshihiro KANEKO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Recently computer networks are widely popularized, where we can easily transfer and duplicate files or data we need. In this situation, large sized files are often compressed in ahead of transfer. The total time from the beginning of compressing a file in some computer (source) till the end of transfering the to other computer (sink) depends on the performances of those computers and the capacity of communication links. If we can compress or decompress files on other computers as well as source and sink, we might transfer files faster than now. On this assumption, a problem of optimal file compression transfer is to choose some computers where we compress and decompress the file in order to transfer these files in the shortest time. Until now, this problem is shown to be reducible to a shortest path problem. Then, by applying familiar shortest path (shortest path tree) algorithm of Dijkstra's to networks with path graph structure, we can solve the problem in polynomical time, but not in linear time. However, if we revise Dijkstra's algorithm, then we can solve the problem for path graph version in linear time, which is shown in this report. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | file compression / shortest path problem / Dijkstra / linear time |
| Paper # | NLP97-77 |
| Date of Issue |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 1997/9/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Nonlinear Problems (NLP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Linear Time Dijkstra Algorithm to Determine Fastest File Transfer on a Fixed Route |
| Sub Title (in English) | |
| Keyword(1) | file compression |
| Keyword(2) | shortest path problem |
| Keyword(3) | Dijkstra |
| Keyword(4) | linear time |
| 1st Author's Name | Satoshi ADACHI |
| 1st Author's Affiliation | Department of Electronics and Computer Engineering, Faculty of Engineering, Gifu University() |
| 2nd Author's Name | Yoshihiro KANEKO |
| 2nd Author's Affiliation | Department of Information Science, Faculty of Engineering, Gifu University |
| Date | 1997/9/18 |
| Paper # | NLP97-77 |
| Volume (vol) | vol.97 |
| Number (no) | 257 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |