On designing constrained local access networks

Author

Dai, H.K. ; Fujino, Shinji

Author_Institution

Dept. of Comput. Sci., Oklahoma State Univ., Stillwater, OK, USA

fYear

2000

fDate

2000

Firstpage

167

Lastpage

176

Abstract

Most network design problems are computationally intractable. For obtaining approximations, greedy heuristics are commonly employed. The Esau-Williams (1966) algorithm adopts a better greedy heuristic in solving the (constrained) capacitated minimum spanning tree (CMST) problem, using a tradeoff function computing the potential saving in the cost of a link. In this study, the component-oriented tradeoff computation is employed instead of the node-oriented one to implement the heuristic efficiently. The improved Esau-Williams algorithm is modified for variations of the CMST problems with order, degree and depth constraints

Keywords

communication complexity; local area networks; trees (mathematics); CMST problems; capacitated minimum spanning tree; component-oriented tradeoff computation; computationally intractable problems; constrained local access network design; degree constraints; depth constraints; greedy heuristics; order constraints; Algorithm design and analysis; Computer networks; Computer science; Cost function; LAN interconnection; Network topology; Spine; Telecommunication traffic; Tree graphs; Wide area networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Networks, 2000. I-SPAN 2000. Proceedings. International Symposium on

Conference_Location

Dallas, TX

ISSN

1087-4089

Print_ISBN

0-7695-0936-3

Type

conf

DOI

10.1109/ISPAN.2000.900282

Filename

900282