Műegyetemi Digitális Archívum
    • magyar
    • English
  • English 
    • magyar
    • English
  • Login
View Item 
  •   DSpace Home
  • 1. Tudományos közlemények, publikációk
  • Periodica Polytechnica archív cikkek
  • View Item
  •   DSpace Home
  • 1. Tudományos közlemények, publikációk
  • Periodica Polytechnica archív cikkek
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Finding Multiple Redundant Trees in Linear Time

Thumbnail
View/Open
99475.pdf (151.1Kb)
Metadata
Show full item record
Link to refer to this document:
http://hdl.handle.net/10890/4175
Collections
  • Periodica Polytechnica archív cikkek [78]
Abstract
Redundant trees are directed spanning trees, which provide disjoint paths towards their roots. Therefore, this concept is widely applied in the literature both for providing protection and load sharing. The fastest algorithm can find multiple redundant trees, a pair of them rooted at each vertex, in linear time. Unfortunately, edge- or vertex-redundant trees can only be found in 2-edge- or 2-vertex-connected graphs respectively. Therefore, the concept of maximally redundant trees was introduced, which can overcome this problem, and provides maximally disjoint paths towards the common root. In this paper, we propose the first linear time algorithm, which can compute a pair of maximally redundant trees rooted at not only one, but at each vertex.
Title
Finding Multiple Redundant Trees in Linear Time
Author
Enyedi, Gábor Sándor
Rétvári, Gábor
Date of issue
2010
Access level
Open access
Publisher
Budapest University of Technology and Economics
Language
en
Page
29 - 40
Subject
redundant trees, maximally redundant trees, independent trees, colored trees, recovery trees, linear, recovery, load sharing
Version
Preprint
Identifiers
MTMT: 2660729
Scopus: 84856920228
Title of the container document
Periodica Polytechnica - Electrical Engineering
Volume of container document
54
Number of container document
1-2
ISSN, e-ISSN
0324-6000
1587-3781
Document type
folyóiratcikk
Document genre
Tudományos cikk

Content by
Theme by 
Atmire NV
DSpace software copyright © 2002-2016  DuraSpace
Contact Us | Send Feedback

Content by
DSpace software copyright © 2002-2016  DuraSpace
Contact Us | Send Feedback
Theme by 
Atmire NV
 

 

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Content by
Theme by 
Atmire NV
DSpace software copyright © 2002-2016  DuraSpace
Contact Us | Send Feedback

Content by
DSpace software copyright © 2002-2016  DuraSpace
Contact Us | Send Feedback
Theme by 
Atmire NV