Cost minimization in redundant trees for protection in vertex-redundant or edge-redundant graphs

Author

Xue, Guoliang ; Chen, Li ; Thulasiraman, K.

Author_Institution

Dept. of Comput. Sci. & Eng., Arizona State Univ., Tempe, AZ, USA

fYear

2002

fDate

2002

Firstpage

187

Lastpage

194

Abstract

Preplanned recovery using redundant trees in vertex-redundant or edge-redundant graphs is extended to the case where each edge has a cost and the goal is to find a pair of working and protection trees such that the cost of the working tree is as low as possible. We present efficient heuristic algorithms for this problem. Extensive computational results show that the cost of the working tree found with our algorithm is within 19% of the cost of a minimum spanning tree on the average, while the smaller cost of the working and protection trees found by the original algorithm without QoS consideration is about 95% over the cost of a minimum spanning tree on the average

Keywords

minimisation; quality of service; telecommunication network reliability; trees (mathematics); QOS; cost minimization; edge-redundant graphs; heuristic algorithms; high speed networks; minimum spanning tree; network protection; network restoration; optimization; protection trees; redundant trees; vertex-redundant graphs; working trees; Computer science; Costs; Heuristic algorithms; High-speed networks; Protection; Quality of service; SONET; Tree graphs; Uniform resource locators; Wavelength division multiplexing;

fLanguage

English

Publisher

ieee

Conference_Titel

Performance, Computing, and Communications Conference, 2002. 21st IEEE International

Conference_Location

Phoenix, AZ

Print_ISBN

0-7803-7371-5

Type

conf

DOI

10.1109/IPCCC.2002.995150

Filename

995150