Efficient associative algorithm to find the least spanning tree of a graph with a node degree constraint

被引：0

作者：

A. Sh. Nepomnyashchaya

机构：

来源：

Cybernetics and Systems Analysis | 1998年 / 34卷

关键词：

Span Tree; Minimum Span Tree; Edge Incident; Matrix Cost; Span Tree Problem;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We have described an associative algorithm to find the smallest spanning tree of a graph with a degree constraint on one of the nodes. The associative algorithm is based on Gabow's algorithm. It is described as a STAR procedure that runs in timeO(@#@ nlogn). This is also the time it takes to construct a minimum spanning tree of a graph on an associative parallel processor [4]. The associative algorithm relies on a number of new constructions that are also useful for other problems. Note that, unlike [13], we use a very simple and natural data representation on an associative parallel processor in the form of two-dimensional binary-coded tables.

引用

页码：77 / 85

页数：8

共 10 条

[1]

Prim R. C.(1957)Shortest connection networks and some generalizations Bell Sys. Tech. J. 36 1389-1401

[2]

Dijkstra E. W.(1959)A note on two problems in connection with graphs Num. Math. 1 269-271

[3]

Kruskal J. B.(1965)On the shortest spanning subtree of a graph and the traveling salesman problem Proc. AMS 7 48-50

[4]

Gabow H. N.(1978)A good algorithm for smallest spanning trees with a degree constraint Networks 8 201-208

[5]

Gabow H. N.(1986)Efficient algorithms for finding minimum spanning trees in undirected and directed graphs Combinatorica 6 109-122

[6]

Galil Z.(1987)Image processing and recognition algorithms for an orthogonal computer Computers and Artificial Intelligence 6 131-149

[7]

Spencer T.(undefined)undefined undefined undefined undefined-undefined

[8]

Tarjan R. E.(undefined)undefined undefined undefined undefined-undefined

[9]

Huebler A.(undefined)undefined undefined undefined undefined-undefined

[10]

Sykora O.(undefined)undefined undefined undefined undefined-undefined

← 1 →