ABSTRACT
The efficient use of modern communication networks depends on our capabilities for solving a number of demanding algorithmic problems, some of which are concerned with the allocation of network resources to individual connections. One of the basic operations in communication networks consists in establishing routes for connection requests between physically separated network endpointsv that wish to establish a connection for information exchange. Many connection requests occur simultaneously in a network, and it is desirable to establish routes for as many requests as possible. In many situations, either due to technical constraints or just to improve the communication, it is required that no two routes interfere with each other, which implies not to share network resources such as links or switches. This scenario can be modeled as follows. Let G = (V, E) be an edge-weighted undirected graph representing a network in which the nodes represent the hosts and switches, and the edges represent the links. Let T = {(sj, tj ) | j = 1, …, 𝕋 sj ≠ tj ∈ V} be a list (of size 𝕋)of commodities, that is, pairs of nodes in G, representing endpoints demanding to be connected by a path in G. T is said to be realizable in G if there exist mutually edge-disjoint (respectively vertex-disjoint) paths from sj to tj in G, for every j = 1, …, 𝕋.
