Publications with Kimberly Crosbie
Maximum plane trees in multipartite geometric graphs.
A. Biniaz,
P. Bose,
J.-L. De Carufel,
K. Crosbie,
D. Eppstein,
A. Maheshwari,
M. Smid.
15th Algorithms and Data Structures Symp. (WADS 2017), St. John's, Newfoundland.
Springer, Lecture
Notes in Comp. Sci. (2017), pp. 193–204.
Algorithmica 81 (4): 1512–1534, 2019.
We consider problems of constructing the maximum-length plane (non-self-crossing) spanning tree on Euclidean graphs given by multicolored point sets, where each point forms a vertex, and each bichromatic pair of points forms an edge with length equal to their Euclidean distance. We show that several such problems can be efficiently approximated.