Oriented Networks Design Problem
Jérôme Galtier, Igor Pesek, Katja Prnaver, Janez Žerovnik · 2010
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 op-timal in terms of costs. The corresponding minimization problem is approached with a local search type heuristics. New local search neighborhood is defined and analyzed.