[Back]


Talks and Poster Presentations (with Proceedings-Entry):

S. Bandyapadhyay, A. Banik, S. Bhore, M. Nöllenburg:
"Geometric Planar Networks on Bichromatic Points";
Talk: CALDAM, Hyderabad , Indien; 2020-02-13 - 2020-02-15; in: "CALDAM: Conference on Algorithms and Discrete Applied Mathematics", LNCS, 12016 (2020), ISBN: 978-3-030-39218-5; 79 - 91.



English abstract:
We study four classical graph problems - Hamiltonian path,
Traveling salesman, Minimum spanning tree, and Minimum perfect
matching on geometric graphs induced by bichromatic (red and blue)
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.


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-39219-2

Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_290105.pdf


Created from the Publication Database of the Vienna University of Technology.