Now showing items 1-6 of 6
Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem
(Springer-Verlag; Springer Science + Business Media Inc., 2004-11)
We consider the problem of finding a minimum diameter spanning treewith maximum node degree $B$ in a complete undirected edge-weightedgraph. We provide an $O(sqrt{log_Bn})$-approximation algorithm for theproblem. Our ...
Better Alternatives to OSPF Routing
(Springer-Verlag; Springer, 2005-08)
The current standard for intra-domain network routing, Open ShortestPath First (OSPF), suffers from a number ofproblems-the tunable parameters (the weights) are hard tooptimize, the chosen paths are not robust underchanges ...
Efficient convexity and domination algorithms for fine- and medium-grain hypercube computers
(Springer-Verlag; Springer-Verlag New York Inc., 1992-12)
This paper gives hypercube algorithms for some simple problems involving geometric properties of sets of points. The properties considered emphasize aspects of convexity and domination. Efficient algorithms are given for ...
Computing convexity properties of images on a pyramid computer
(Springer-Verlag; Springer-Verlag New York Inc., 1991-12)
We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying ...
A linear-time algorithm for constructing a circular visibility diagram
(Springer-Verlag; Springer-Verlag New York Inc., 1995-09)
To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of ...
Average Case Analysis of Gosper’s Algorithm for aClass of Urn Model Inputs
(Springer-Verlag; Springer, 2005-09)
In this paper we perform an asymptotic average case analysis of some of the most important steps of Gosper’s algorithm for indefinite summation of hypergeometric terms. The space of input functions of the algorithm is ...