dc.contributor.author | Bandyapadhyay, Sayan | |
dc.contributor.author | Banik, Aritra | |
dc.contributor.author | Bhore, Sujoy | |
dc.contributor.author | Nollenburg, Martin | |
dc.date.accessioned | 2021-06-02T09:50:09Z | |
dc.date.available | 2021-06-02T09:50:09Z | |
dc.date.created | 2020-10-22T16:55:08Z | |
dc.date.issued | 2020 | |
dc.Published | Lecture Notes in Computer Science (LNCS). 2020, 12016 LNCS 79-91. | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.uri | https://hdl.handle.net/11250/2757344 | |
dc.description.abstract | 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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Springer | en_US |
dc.title | Geometric Planar Networks on Bichromatic Points | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | acceptedVersion | en_US |
dc.rights.holder | Copyright Springer Nature Switzerland AG 2020 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.fulltext | postprint | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.1007/978-3-030-39219-2_7 | |
dc.identifier.cristin | 1841622 | |
dc.source.journal | Lecture Notes in Computer Science (LNCS) | en_US |
dc.source.40 | 12016 LNCS | |
dc.source.pagenumber | 79-91 | en_US |
dc.identifier.citation | Lecture Notes in Computer Science (LNCS). 2020, 12016, 79-91 | en_US |
dc.source.volume | 12016 | en_US |