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] |

¡@

JEROME GALTIER^{1}, IGOR PESEK^{2}, KATJA PRNAVER^{3} AND JANEZ ZEROVNIK^{3,4}

*
^{1}Orange Labs 905 rue Albert Einstein
06921 Sophia Antipolis Cedex, France
^{2}Faculty of Natural Sciences and Mathematics
University of Maribor
Koroska 160,2000 Maribor, Slovenia
^{3}Institute of Mathematics, Physics and Mechanics
Jadranska 19, 1000 Ljubljana, Slovenia
^{4}Faculty 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 (**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.