Ricerc@Sapienza

We present graph-theoretic characterisations of three notions of inefficiency arising in network models: edge-weakness in flow networks, node-weakness in depletable channels, and vulnerability in traffic networks. Our characterisations lead to three polynomial algorithms that check these forms of inefficiency. Furthermore, checking vulnerability also leads to an advancement on the subgraph homeomorphism problem.

We consider three network models where information items flow from a source to a sink node: flow networks, depletable channels, and traffic networks. We start with the standard model of flow networks; we characterise graph topologies that admit non-maximum saturating flows, under some capacity-to-edge assignment. We then consider a model where routing is constrained by energy available on nodes in finite supply (like in Smartdust) and efficiency is related to energy consumption and again to maximality of saturating flows.