NOTE ON FINDING OPTIMUM BRANCHINGS

被引：55

作者：

CAMERINI, PM

FRATTA, L

MAFFIOLI, F

机构：

[1] Centro Studi per le Telecomunicazioni, CNR, Istituto di Elettrotecnica ed Elettronica, Politecnico di Milano, Milano

来源：

NETWORKS | 1979年 / 9卷 / 04期

关键词：

D O I：

10.1002/net.3230090403

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The subject of this note is Tarjan's algorithm for finding an optimum branching in a directed graph. Two errors are pointed out, namely (i) an incorrect claim involving branching uniqueness, and (ii) an imprecise way of updating edge values in each iteration. These two inaccuracies do not affect the basic validity of the algorithm. It is shown here that they may be fixed via a simple modification, which leaves unchanged the overall time and space performances. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company

引用

页码：309 / 312

页数：4

共 9 条

[1]

Aho A.V., Hopcroft J.E., Ullman J.D., On Finding Optimum Ancestors in Trees, SIAM Journal on Computing, 5, pp. 115-132, (1976)

[2]

Bock F., An Algorithm to Construct a Minimum Directed Spanning Tree in a Directed Network, Developments in Operations Research, pp. 29-44, (1971)

[3]

Camerini P.M., Fratta L., Maffioli F.

[4]

Cheriton D., Tarjan R., Finding Minimum Spanning Trees, SIAM Journal on Computing, 5, pp. 724-742, (1976)

[5]

Chu Y.J., Lin T.H., On the Shortest Arborescence of a Directed Graph, Sci. Sinica, 14, pp. 1396-1400, (1965)

[6]

Edmonds J., Optimum Branchings, Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 71 B, pp. 233-240, (1967)

[7]

Karp R.M., A Simple Derivation of Edmonds' Algorithm for Optimum Branchings, Networks, 1, pp. 265-272, (1971)

[8]

Tarjan R.E., Finding Optimum Branchings, Networks, 7, pp. 25-35, (1977)

[9]

Tarjan R.E.

← 1 →