Library

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
  • 1
    Electronic Resource
    Electronic Resource
    Probabilistic analysis of a grouping algorithm (1991)
    Springer
    Algorithmica 6 (1991), S. 192-206 
    Details
    ISSN: 1432-0541
    Keywords: Probabilistic analysis of algorithms ; Grouping by swapping ; Memory compaction ; Exponential of a matrix
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study thegrouping by swapping problem, which occurs in memory compaction and in computing the exponential of a matrix. In this problem we are given a sequence ofn numbers drawn from {0,1, 2,...,m−1} with repetitions allowed; we are to rearrange them, using as few swaps of adjacent elements as possible, into an order such that all the like numbers are grouped together. It is known that this problem is NP-hard. We present a probabilistic analysis of a grouping algorithm calledMEDIAN that works by sorting the numbers in the sequence according to their median positions. Our results show that the expected behavior ofMEDIAN is within 10% of optimal and is asymptotically optimal asn/m→∞ or asn/m→0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759041
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Stochastic rearrangement rules for self-organizing data structures (1991)
    Springer
    Algorithmica 6 (1991), S. 278-291 
    Details
    ISSN: 1432-0541
    Keywords: Self-organizing data structures ; Move-to-front heuristic
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider self-organizing data structures when the number of data accesses is unknown. We show that certain general rearrangement rules can be modified to reduce significantly the number of data moves, without affecting the asymptotic cost of a data access. As a special case, explicit formulae are given for the expected cost of a data access and the expected number of data moves for the modified move-to-front rules for linear lists and binary trees. Since a data move usually costs at least as much as a data access, the modified rule eventually leads to a savings in total cost (the sum of data accesses and moves).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01759046
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    On the time required to detect cycles and connectivity in graphs (1972)
    Springer
    Theory of computing systems 6 (1972), S. 103-106 
    Details
    ISSN: 1433-0490
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract It is shown that when a graph is represented as a binary connection matrix, the problems of finding the shortest path between two nodes of a graph, of determining whether the graph has a cycle, and of determining if a graph is strongly connected each require at leastO(n 2) operations. Thus the presently known best algorithms are optimal to within a multiplicative constant.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01706081
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    The complexity of drawing trees nicely (1983)
    Springer
    Acta informatica 18 (1983), S. 377-392 
    Details
    ISSN: 1432-0525
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Summary We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious “principle of optimality” that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are Θ(n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00289576
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Book
    Book
    Combinatorial algorithms: theory and practice (1977)
    Englewood Cliffs, NJ :Prentice-Hall,
    Details
    Title: Combinatorial algorithms: theory and practice
    Author: Reingold, Edward M.
    Contributer: Nievergelt, Jurg , Deo, Narsingh
    Publisher: Englewood Cliffs, NJ :Prentice-Hall,
    Year of publication: 1977
    Pages: 433 S.
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...