JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24]


Journal of Information Science and Engineering, Vol. 26 No. 4, pp. 1231-1242


Oriented Networks Design Problem

JEROME GALTIER1, IGOR PESEK2, KATJA PRNAVER3 AND JANEZ ZEROVNIK3,4
1Orange Labs 905 rue Albert Einstein 
06921 Sophia Antipolis Cedex, France 
2Faculty of Natural Sciences and Mathematics 
University of Maribor 
Koroska 160,2000 Maribor, Slovenia 
3Institute of Mathematics, Physics and Mechanics 
Jadranska 19, 1000 Ljubljana, Slovenia 
4Faculty of Mechanical Engineering 
University of Ljubljana 
Askerceva 6, 1000 Ljubljana, Slovenia

    The design of interconnection networks is very popular in computer science. In this paper we introduce a novel problem, the design of oriented networks. The underlying structure of such networks is a directed graph with weights on the arcs, which are the number of paths of the routing that traverse the arc. The cost of a network with a routing is defined as a sum of arc costs that are computed with concave increasing cost function depending on weights over directed arcs. The objective is to find the routing that is optimal in terms of costs. The corresponding minimization problem is approached with a local search type heuristics. New local search neighborhood is defined and analyzed.

Keywords: oriented networks problem, heuristics, local search, hill climbing, SDH networks

  Retrieve PDF document (JISE_201004_05.pdf)