On k-Connectivity Problems in Distributed Systems
Book chapter > Chapter Other Book · 2016
Authors: Vahıd AKRAM, Orhan DAĞDEVİREN
Advances in Wireless Technologies and Telecommunication, Chapter Other Book, IGI Global, B, International, 2016, pp 30-57, ,
DOI: 10.4018/978-1-4666-9964-9.ch002
Summary
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.