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, doi:10.1007/978-3-319-62127-2_17.
Algorithmica 81 (4): 1512–1534, 2019, doi:10.1007/s00453-018-0482-x.
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.