Premium
Multiterminal resilience for series‐parallel networks
Author(s) -
Farley Toni R.,
Colbourn Charles J.
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20186
Subject(s) - social connectedness , resilience (materials science) , computer science , reliability (semiconductor) , measure (data warehouse) , series (stratigraphy) , terminal (telecommunication) , mobile ad hoc network , theoretical computer science , computer network , data mining , psychology , paleontology , power (physics) , physics , quantum mechanics , biology , network packet , psychotherapist , thermodynamics
Network resilience measures the average two‐terminal reliability (connectedness) of a network. Multiterminal resilience extends this measure to any k vertices; it is the average k ‐terminal reliability of a network. This generalizes two well‐studied network connectedness measures. Calculating multiterminal resilience on general networks encompasses all‐terminal reliability and thus is NP‐hard. Multiterminal resilience is examined on undirected series‐parallel networks, and an efficient (polynomial time) algorithm is developed for calculating the resilience for every k . Applications in mobile ad hoc and sensor networks are outlined. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 164–172 2007