• norsk
    • English
  • English 
    • norsk
    • English
  • Login
View Item 
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
  •   Home
  • University of Bergen Library
  • Registrations from Cristin
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Geometric Planar Networks on Bichromatic Points

Bandyapadhyay, Sayan; Banik, Aritra; Bhore, Sujoy; Nollenburg, Martin
Journal article, Peer reviewed
Accepted version
Thumbnail
View/Open
Accepted Version (567.0Kb)
URI
https://hdl.handle.net/11250/2757344
Date
2020
Metadata
Show full item record
Collections
  • Department of Informatics [1076]
  • Registrations from Cristin [12943]
Original version
Lecture Notes in Computer Science (LNCS). 2020, 12016, 79-91   10.1007/978-3-030-39219-2_7
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.
Publisher
Springer
Journal
Lecture Notes in Computer Science (LNCS)
Copyright
Copyright Springer Nature Switzerland AG 2020

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit
 

 

Browse

ArchiveCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsDocument TypesJournalsThis CollectionBy Issue DateAuthorsTitlesSubjectsDocument TypesJournals

My Account

Login

Statistics

View Usage Statistics

Contact Us | Send Feedback

Privacy policy
DSpace software copyright © 2002-2019  DuraSpace

Service from  Unit