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.