Connectivity graphs of uncertainty regions

Details Connectivity graphs of uncertainty regions Connectivity graphs of uncertainty regions

2010-09-17

arxiv.org/abs/1009.3469v2

Computer Science

Computational Geometry

26 pages, 15 figures, full version of extended abstract that is to appear in ISAAC 2010. (Modification: added full appendix wi

Scientific paper

We study a generalization of the well known bottleneck spanning tree problem called "Best Case Connectivity with Uncertainty": Given a family of geometric regions, choose one point per region, such that the length of the longest edge in a spanning tree of a disc intersection graph is minimized. We show that this problem is NP-hard even for very simple scenarios such as line segments and squares. We also give exact and approximation algorithms for the case of line segments and unit discs respectively.

Affiliated with

Also associated with

No associations

Rating

Connectivity graphs of uncertainty regions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Connectivity graphs of uncertainty regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity graphs of uncertainty regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-442640