Geometric Planar Networks on Bichromatic Points
Journal article, Peer reviewed
Accepted version
Permanent lenke
https://hdl.handle.net/11250/2757344Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
- Department of Informatics [981]
- Registrations from Cristin [10412]
Originalversjon
Lecture Notes in Computer Science (LNCS). 2020, 12016, 79-91 10.1007/978-3-030-39219-2_7Sammendrag
We study four classical graph problems – Hamiltonian path, Traveling salesman, Minimum spanning tree, and Minimum perfect matching on geometric graphs induced by bichromatic ( Open image in new window and Open image in new window ) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP -hard. In this work, we consider these problems in two restricted settings: (i) collinear points and (ii) equidistant points on a circle. We show that almost all of these problems can be solved in linear time in these constrained, yet non-trivial settings.