×

Enumerating the \(k\) best plane spanning trees. (English) Zbl 0976.68161

Summary: A spanning tree constructed of straight line segments over a set of points in the Euclidean plane is called “non-crossing” or “plane tree”, if no two segments intersect. Imposing the additional constraint of non-crossing segments makes many combinatorial geometric problems harder. In the case of plane spanning trees, however, we show that they can be enumerated efficiently in the order of their total length. This makes it possible to efficiently find the \(k\) best plane trees, or all those shorter than a given bound.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science

Keywords:

spanning tree

Software:

ZRAM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Avis, D.; Fukuda, K., Reverse search for enumeration, Discrete Appl. Math., 65, 21-46 (1996) · Zbl 0854.68070
[2] Brüngger, A.; Marzetta, A.; Fukuda, K.; Nievergelt, J., The parallel search bench ZRAM and its applications, Ann. Oper. Res., Special Issue on Parallel Optimization, 90, 45-63 (1999) · Zbl 0937.90088
[3] Camerini, P. M.; Fratta, L.; Maffioli, F., The \(K\) best spanning arborescences of a network, Networks, 10, 2, 91-109 (1980) · Zbl 0435.68050
[4] Gabow, H. N., Two algorithms for generating weighted spanning trees in order, SIAM J. Comput., 6, 139-150 (1977) · Zbl 0346.68021
[5] Katoh, N.; Ibaraki, T.; Mine, H., Algorithms for finding \(k\) minimum spanning trees, SIAM J. Comput., 10, 247-255 (1981) · Zbl 0456.68075
[6] Marzetta, A., ZRAM: A library of parallel search algorithms and its use in enumeration and combinatorial optimization, Dissertation (1998), ETH Zurich
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.