On k-Connectivity Problems in Distributed Systems
Kitapta bölümler > Diğer · 2016
Yazarlar: Vahıd AKRAM, Orhan DAĞDEVİREN
Advances in Wireless Technologies and Telecommunication, Diğer, IGI Global, B, Uluslararası, 2016, ss 30-57, ,
DOI: 10.4018/978-1-4666-9964-9.ch002
Özet
k-Connectivity detection and restoration are important problems in graph theory and computer networks. A graph is k-connected if it remains connected after removing k-1 arbitrary nodes. The k-connectivity is an important property of a distributed system because a k-connected network can tolerate k-1 node failures without losing the network connectivity. To achieve the k-connectivity in a network, we need to determine the current connectivity value and try to increase connectivity if the current k is lower than the desired value. This chapter reviews the central and distributed algorithms for detecting and restoring the k-connectivity in graphs and distributed systems. The algorithms will be compared from complexity, accuracy and efficiency perspectives.