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.
Graph theoretic detection of inefficiencies in network models / Salvo, Ivano; Gorla, Daniele; Cenciarelli, Pietro. - 2243:(2018), pp. 87-91. (Intervento presentato al convegno 19th Italian Conference on Theoretical Computer Science, ICTCS 2018 tenutosi a ita).
Graph theoretic detection of inefficiencies in network models
Salvo, Ivano
;Gorla, Daniele;Cenciarelli, Pietro
2018
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
