PROPERTIES OF LABELING METHODS FOR DETERMINING SHORTEST-PATH TREES

被引：22

作者：

SHIER, DR ^{[1
]}

WITZGALL, C ^{[1
]}

机构：

[1] NBS, WASHINGTON, DC 20234 USA

来源：

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS | 1981年 / 86卷 / 03期

关键词：

D O I：

10.6028/jres.086.013

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

A number of labeling procedures for determining shortest paths in a network employ a sequence list in order to carry out the required steps systematically. A study is made of certain formal properties of such sequence lists. It is shown that the desirable property of branching out from nodes whose labels represent actual in-tree distances is assured for certain ways of managing the sequence list, but not for others. The relationship of this property to the computational complexity of various labeling procedures is also investigated.

引用

页码：317 / 330

页数：14

共 14 条

[1]

BARR R, 1979, INFOR, V17, P16

[2] COMPUTATIONAL ANALYSIS OF ALTERNATIVE ALGORITHMS AND LABELING TECHNIQUES FOR FINDING SHORTEST PATH TREES [J].