Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed connectivity algorithms
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
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. , p. 130
Series
Doctoral thesis / Luleå University of Technology 1 jan 1997 → …, ISSN 1402-1544 ; 1997:20
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-17040Local ID: 141a7db0-86b3-11db-8975-000ea68e967bOAI: oai:DiVA.org:ltu-17040DiVA: diva2:990033
Note

Godkänd; 1997; 20061128 (haneit)

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

Open Access in DiVA

No full text in DiVA

By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 48 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf