๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal time bounds for some proximity problems in the plane

โœ Scribed by Alok Aggarwal; Herbert Edelsbrunner; Prahakar Raghavan; Prasoon Tiwari

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
507 KB
Volume
42
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Asymptotically Optimal Bounds for OBDDs
Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems
โœ Beate Bollig; Ingo Wegener ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 262 KB

Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, and computer aided design. For many functions it is easy to estimate the OBDD size but asym

An approximation scheme for some Steiner
An approximation scheme for some Steiner tree problems in the plane
โœ Wang, Lusheng; Jiang, Tao ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 536 KB

We design a polynomial-time approximation scheme for the Steiner tree problem in the plane when the given set of regular points is c-local, i.e., in the minimum-cost spanning tree for the given set of regular points, the length of the longest edge is at most c times the length of the shortest edge.

Time Bounds for Decision Problems in the
Time Bounds for Decision Problems in the Presence of Timing Uncertainty and Failures
โœ Hagit Attiya; Taly Djerassi-Shintel ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 182 KB

This paper studies the time complexity of solving decision problems in a distributed message-passing system when there is inexact information about time and process failures. A semi-synchronous model is assumed, in which the amount of (real) time between two consecutive steps of a nonfaulty process