Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
S. Bandyapadhyay, A. Banik, S. Bhore, M. Nöllenburg:
"Geometric Planar Networks on Bichromatic Points";
Vortrag: CALDAM,
Hyderabad , Indien;
13.02.2020
- 15.02.2020; in: "CALDAM: Conference on Algorithms and Discrete Applied Mathematics",
LNCS,
12016
(2020),
ISBN: 978-3-030-39218-5;
S. 79
- 91.
Kurzfassung englisch:
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.
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-39219-2
Elektronische Version der Publikation:
https://publik.tuwien.ac.at/files/publik_290105.pdf
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.