ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Books
  • Articles  (9)
  • Data
  • F.2.2  (9)
  • 1995-1999
  • 1985-1989  (9)
  • 1950-1954
  • 1988  (9)
  • Mathematics  (9)
Collection
  • Books
  • Articles  (9)
  • Data
Source
Keywords
Publisher
Years
  • 1995-1999
  • 1985-1989  (9)
  • 1950-1954
Year
Topic
  • Mathematics  (9)
  • 1
    Electronic Resource
    Electronic Resource
    Greedy matching on a grid (1988)
    Springer
    BIT 28 (1988), S. 19-26 
    Details
    ISSN: 1572-9125
    Keywords: E.2 ; F.2.2 ; complete matching ; greedy heuristic ; nearest neighbor searching ; semi-dynamic data structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A fast solution to the complete minimum matching problem using a greedy heuristic is presented, when the points are distributed on a grid domain. For this a data structure which efficiently supports nearest neighbor searches and deletions from a planar point set is developed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934691
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    A note on the largest empty rectangle problem (1988)
    Springer
    BIT 28 (1988), S. 179-183 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; G.2.2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog3 n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog2 n) algorithm for our problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934704
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    AVLSI partition algorithm (1988)
    Springer
    BIT 28 (1988), S. 215-226 
    Details
    ISSN: 1572-9125
    Keywords: B.7.1 ; F.2.2 ; Sorting ; Quicksort ; Partition ; VLSI algorithms ; VLSI sorters
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A VLSI sorter of sizeO(n) can sortn elements in linear time when the input and output time are taken into account. If the input contains more thann elements, some prepocessing has to be performed. A VLSI partition algorithm that provides a solution to this problem is presented. The algorithm partitions the input data into two smaller parts as the quicksort algorithm does. That is, the elements of the first part will be smaller than the elements of the second part. The partition is repeated until the parts are small enough to fit in the sorter. It is shown that the average number of times each element must go through the partitioner isO(logk) for a data file of sizekn wheren is the size of the sorter. In the worst case where the partitioner fails to divide the input evenly, the elements must goO(k) times through the partitioner like in the quicksort algorithm. The partitioner can also be used, with simple modifications, as a sorter, a stack, a queue, or as a priority queue. Other advantages of the VLSI algorithm are also discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934087
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Scanline algorithms on a grid (1988)
    Springer
    BIT 28 (1988), S. 227-241 
    Details
    ISSN: 1572-9125
    Keywords: E.2 ; F.2.2 ; scanline techniques ; grid geometry ; maximal elements ; rectangle problems ; connected components ; line segment intersection
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the time complexity of solutions to the maximal elements and closure problems, a factor logn is substituted by loglogn, wheren is the number of elements. Next, by using a data structure introduced in the paper, the interval trie, previous solutions to the rectangle intersection and connected component problems are improved upon. Finally, a fast intersection finding algorithm for arbitrarily oriented line segments is presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    An optimal time algorithm for finding a maximum weight independent set in a tree (1988)
    Springer
    BIT 28 (1988), S. 353-356 
    Details
    ISSN: 1572-9125
    Keywords: G.2.2 ; F.2.2 ; maximum weight independent set ; dynamic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934098
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Linear open addressing and Peterson's theorem rehashed (1988)
    Springer
    BIT 28 (1988), S. 364-371 
    Details
    ISSN: 1572-9125
    Keywords: E.1 ; F.2.2 ; hashing ; open addressing ; clustering
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01934101
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A select and insert sorting algorithm (1988)
    Springer
    BIT 28 (1988), S. 725-735 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; G.2.1 ; Sorting algorithms ; complexity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A general sorting algorithm, having the well knownO(n 2) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n 1.5) and a worst case complexity ofO(n 2). However, making random choices (by some random number generator) is time consuming, and a simple “quasi-random” scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n 1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01954893
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    On the distribution of comparisons in sorting algorithms (1988)
    Springer
    BIT 28 (1988), S. 764-774 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; Sorting ; lower bounds ; adversaries
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We considered the following natural conjecture: For every sorting algorithm every key will be involved inΩ(logn) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involven−n ε /2+1 keys in at leastεlog2 n comparisons,ε〉0. Further, there exists a sorting algorithm that will for every input involve at mostn−n ε/c keys in greater thanεlog2 n comparisons, wherec is a constant andε〉0. The conjecture is shown to hold for “natural” algorithms from the literature.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01954896
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Encroaching lists as a measure of presortedness (1988)
    Springer
    BIT 28 (1988), S. 775-784 
    Details
    ISSN: 1572-9125
    Keywords: F.2.2 ; 68R05 ; sorting ; presortedness ; encroaching lists ; melsort ; permutations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such listsm provides a measure of presortedness with advantages over others in the literature. Experimental and analytic results are presented to cast light on the properties of encroaching lists. Also, we describe a new sorting algorithm,melsort, with complexityO(nlogm). Thus it is linear for well ordered sets and reduces to mergesort andO(nlogn) in the worst case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01954897
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...