Finding Multiple Redundant Trees in Linear Time

View/ Open
Metadata
Show full item record
Link to refer to this document:
Collections
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