On The Computation Of Fast Data Transmissions In Networks With Capacities And Delays

    Authors

    D. Kagaris; G. E. Pantziou; S. Tragoudas;C. D. Zaroliagis

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Keywords

    QUICKEST PATH PROBLEM; ALGORITHMS; Computer Science, Theory & Methods

    Abstract

    We examine the problem of transmitting in minimum time a given amount of data between a source and a destination in a network with finite channel capacities and non-sere propagation delays. In the absence of delays, the problem has been shown to be solvable in polynomial time. In this paper, we show that the general problem is NP-hard. In addition, we examine transmissions along a single path, called the quickest path, and present algorithms for general and sparse networks that outperform previous approaches. The first dynamic algorithm for the quickest path problem is also given.

    Journal Title

    Algorithms and Data Structures

    Volume

    955

    Publication Date

    1-1-1995

    Document Type

    Article

    Language

    English

    First Page

    291

    Last Page

    302

    WOS Identifier

    WOS:A1995BE73K00026

    ISSN

    0302-9743; 3-540-60220-8

    Share

    COinS