Previous [ 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 (July 2010)

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

Full Text () Retrieve PDF document (201007_05.pdf)

Received July 11, 2008; revised October 20, 2008 & January 5 & May 7 & June 19 2009; accepted July 10, 2009.
Communicated by Nancy M. Amato.