Cheapest Paths in Multi-Interface Networks

Multi-interface networks are characterized by the property that each node in the network might choose among several communication interfaces in order to establish desired connections. A connection between two neighboring nodes is established if they both activate a common interface. Each interface is associated with an activation cost. In this context we investigate on the so called Cheapest Paths. I.e., given a node s of the network, for each other node j, we look for the cheapest set of interfaces that must be activated among the nodes in order to establish a path between s and j. Polynomial algorithms are provided.