Change search
ReferencesLink to record
Permanent link

Direct link
Distributed connectivity algorithms
Luleå tekniska universitet.
1997 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The goal of this research is to design efficient distributed algorithms which execute on an arbitrary network to recognize special connectivity structures within that network. In some cases, we also consider the maintenance of these special structures in dynamically changing networks. Connectivity information is useful because it is a measure of network reliability. This information is also useful in optimizing distributed applications and control algorithms. We consider asynchronous point-to-point communication networks where a network is represented by an undirected simple graph G. We begin with the problem of finding a core of a network. A core is a path which minimizes the total distance from other vertices to the vertices on the path. This problem is NP-complete for arbitrary networks. We study this problem while restricting the network topology to trees. The minimum cycle cover problem is to find a set of simple cycles which covers a graph such that the size of the cover is minimized. This problem is conjectured to be NP-complete. We present a distributed algorithm which finds a small cycle cover. We propose dynamic algorithms which identify critical links and maximal k-edge-connected components (k = 2,3). The critical links are those which must be kept functional so that the network does not become disconnected. A k-edge-connected component is a maximal subset of vertices H of G such that for any pair of vertices in H, there are k edge disjoint paths between them in G. By identifying k-edge-connected components, the inherent connectivity structure of the network becomes apparent. We study the problem of finding a sparse certificate which can be used to test k-connectivity.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 1997. , 130 p.
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 1997:20
Research subject
Dependable Communication and Computation Systems
URN: urn:nbn:se:ltu:diva-17040Local ID: 141a7db0-86b3-11db-8975-000ea68e967bOAI: diva2:990033

Godkänd; 1997; 20061128 (haneit)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2016-10-19Bibliographically approved

Open Access in DiVA

No full text

Search outside of DiVA

GoogleGoogle ScholarTotal: 1 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link