Time complexity of a path formulated optimal routing algorithm (second printing)

Author

Antonio, John K. ; Tsai, Wei K. ; Huang, G.M.

Author_Institution

Sch. of Electr. Eng., Purdue Univ., West Lafayette, IN, USA

Volume

39

Issue

9

fYear

1994

fDate

9/1/1994 12:00:00 AM

Firstpage

1839

Lastpage

1844

Abstract

A detailed analysis of convergence rate is presented for an iterative path formulated optimal routing algorithm. In particular, it is quantified, analytically, how the convergence rate changes as the number of nodes in the underlying graph increases. The analysis is motivated by a particular path formulated gradient projection algorithm that has demonstrated excellent convergence rate properties through extensive numerical studies. The analytical result proven in this note is that the number of iterations for convergence depends on the number of nodes only through the network diameter

Keywords

computational complexity; convergence of numerical methods; graph theory; iterative methods; numerical analysis; optimisation; convergence rate; network diameter; path formulated gradient projection algorithm; path formulated optimal routing algorithm; time complexity; underlying graph; Algorithm design and analysis; Convergence; Delay estimation; Equations; Iterative algorithms; Printing; Projection algorithms; Routing; Telecommunication traffic; Traffic control;

fLanguage

English

Journal_Title

Automatic Control, IEEE Transactions on

Publisher

ieee

ISSN

0018-9286

Type

jour

DOI

10.1109/9.317108

Filename

317108