Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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 algorithms for finding small cycle covers in arbitrary networks
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Department of Computer ScienceMasaryk University, Brno, Czech Republic.
1994 (English)In: Algorithms and computation: proceedings : 5th international symposium, ISAAC '94, Beijing, P. R. China, August 25 - 27 / [ed] Ding-Zhu Du, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 110-118Conference paper, Published paper (Refereed)
Abstract [en]

Given an arbitrary (bridgeless) network G=(V, E), we develop a distributed algorithm which runs on the network itself to find a small cycle cover for the network, using only local knowledge and message passing. A cycle cover C of G is a set of cycles such that every edge of E is contained in at least one cycle in C. Although the minimum cycle cover problem is conjectured to be N P-complete, our algorithm guarantees a small cycle cover of O(m + n log n) size, where n and m are the number of processors V and communication links E in the network respectively. In an asynchronous bounded delay network where message length is O(log n) bits, the algorithm requires O(n log n) time and O(mn + n 2 log n) messages in the worst case.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994. p. 110-118
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 834
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-31905DOI: 10.1007/3-540-58325-4_172Local ID: 63aaf0a0-c0cd-11df-a707-000ea68e967bISBN: 3-540-58325-4 (print)OAI: oai:DiVA.org:ltu-31905DiVA, id: diva2:1005139
Conference
International Symposium on Algorithms and Computation : 25/08/1994 - 27/08/1994
Note

Godkänd; 1994; 20100915 (andbra)

Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2018-01-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Carr-Motyckova, Lenka

Search in DiVA

By author/editor
Carr-Motyckova, Lenka
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 7 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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