Inefficiencies in network models: a graph-theoretic perspective
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.