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
    Randomized competitive algorithms for the list update problem (1994)
    Springer
    Algorithmica 11 (1994), S. 15-32 
    Details
    ISSN: 1432-0541
    Keywords: Sequential search ; List-update ; On-line algorithms ; Competitive analysis ; Randomized algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01294261
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Maintaining bridge-connected and biconnected components on-line (1992)
    Springer
    Algorithmica 7 (1992), S. 433-464 
    Details
    ISSN: 1432-0541
    Keywords: On-line algorithms ; Graph algorithms ; Graph connectivity ; Dynamic trees ; Data structures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the twin problems of maintaining the bridge-connected components and the biconnected components of a dynamic undirected graph. The allowed changes to the graph are vertex and edge insertions. We give an algorithm for each problem. With simple data structures, each algorithm runs inO(n logn +m) time, wheren is the number of vertices andm is the number of operations. We develop a modified version of the dynamic trees of Sleator and Tarjan that is suitable for efficient recursive algorithms, and use it to reduce the running time of the algorithms for both problems toO(mα(m,n)), where α is a functional inverse of Ackermann's function. This time bound is optimal. All of the algorithms useO(n) space.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01758773
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs (1994)
    Springer
    Algorithmica 11 (1994), S. 341-352 
    Details
    ISSN: 1432-0541
    Keywords: Sensitivity analysis ; Minimum spanning tree ; Network optimization ; Planar graphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its replacement edges, and to verify its minimality. It can also be used to analyze the sensitivity of a single-source shortest-path tree to changes in edge costs, and to analyze the sensitivity of a minimum-cost network flow. The algorithm is simple and practical. It uses the properties of a planar embedding, combined with a heap-ordered queue data structure.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01187017
    Library Location Call Number Volume/Issue/Year 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...