| Enumerating Constrained Non-crossing Geometric Spanning Trees (Computing and Combinatorics) (2007) | |||||||||||||||
Abstract | |||||||||||||||
| Computing and combinatorics : 13th Annual International Conference, COCOON 2007 Banff, Canada, July 16-19, 2007 : proceedings : (Lecture notes in computer science ; 4598). Proc. of 13th Annual International Computing and Combinatorics Conference (COCOON 2007) LNCS 4598. In this paper we present an algorithm for enumerating without repetitions all non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraints (i.e., some edges are required to be included in spanning trees). We will first prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the constrained smallest indexed triangulation which is obtained by extending the lexicographically ordered triangulation introduced by Bespamyatnikh. More specifically, we prove that all edge-constrained triangulations can be transformed to the smallest indexed triangulation among them by O(n 2) times of greedy flips. Our enumeration algorithm generates each output graph in O(n 2) time and O(n) space based on reverse search technique. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||