On‐line connectivity algorithms
作者:
Grant A. Cheston,
期刊:
Networks
(WILEY Available online 1984)
卷期:
Volume 14,
issue 1
页码: 83-94
ISSN:0028-3045
年代: 1984
DOI:10.1002/net.3230140108
出版商: Wiley Subscription Services, Inc., A Wiley Company
数据来源: WILEY
摘要:
AbstractThe problem is to be able to respond to inquiries of the form “Are verticesuandvof graphGconnected?” as quickly as possible in an on‐line situation where edges are being inserted into and deleted from the graph. Recently Even and Shiloach presented a data structure and algorithm involving three synchronized processes to handle the deletion case. An alternative algorithm, LEVELS, is presented to update their data structure. This algorithm is more efficient than theirs and has the further feature of not requiring synchronized processes, so that it is much easier to implement. Finally the LEVELS algorithm is compared to and contrasted with an algorithm using a spanning‐forest data structure for both edge insertion and deletion. The LEVELS algorithm appears to be better for deletion, while the spanning‐forest algorithm is better for
点击下载:
PDF
(614KB)
返 回