Connectivity graphs of uncertainty regions

DOI10.1007/s00453-016-0191-2zbMath1372.68205arXiv1009.3469OpenAlexW2155406096MaRDI QIDQ2408099

Jeff Sember, Ulrike Stege, Venkatesh Srinivasan, Alejandro Erickson, Christophe Weibel, Jonathan Lenchner, Svetlana Stolpner, Erin Wolf Chambers, Sándor P. Fekete, S. H. Whitesides, Srinivasan Venkatesh

Publication date: 9 October 2017

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.3469

zbMATH Keywords

uncertaintyconnectivitygeometric optimizationbest-case connectivityworst-case connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

Connectivity graphs of uncertainty regions ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Unnamed Item ⋮ Dispersing points on intervals ⋮ On minimum- and maximum-weight minimum spanning trees with neighborhoods

Cites Work

• Guaranteed performance heuristics for the bottleneck traveling salesman problem
• Largest and smallest convex hulls for imprecise points
• Representing a planar graph by vertical lines joining different levels
• Rectilinear planar layouts and bipolar orientations of planar graphs
• Approximation algorithms for the Geometric Covering Salesman Problem
• Structural tolerance and Delaunay triangulation
• Systems of distant representatives
• Largest bounding box, smallest diameter, and related problems on imprecise points
• Connectivity graphs of uncertainty regions
• Polynomial time approximation schemes for base station coverage with minimum total radii
• On Minimum-and Maximum-Weight Minimum Spanning Trees with Neighborhoods
• Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
• Rectilinear Shortest Path and Rectilinear Minimum Spanning Tree with Neighborhoods
• On the Hardness of Range Assignment Problems
• Touring a sequence of polygons
• Planar Formulae and Their Uses
• Convex Transversals
• Minimum Spanning Tree with Neighborhoods
• TSP with neighborhoods of varying size
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Connectivity graphs of uncertainty regions