𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A complete spanning tree maintenance algorithm and its complexity

✍ Scribed by Akinori Saitoh; Yoshihiro Tsujino; Nobuki Tokura

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
891 KB
Volume
23
Category
Article
ISSN
0882-1666

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The spanning tree maintenance problem for an LAN model in which node processors may halt and recover is considered. An algorithm meeting the conditions that the spanning tree is an L‐ary complete tree and that nodes halt or recover singly is presented. The message complexity of this algorithm is shown to be comparable with local computational complexity.

πŸ“œ SIMILAR VOLUMES

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami