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. ( 19th Italian Conference on Theoretical Computer Science, ICTCS 2018 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.File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
