Skip to main content

8 Result(s)

within Daniel D. Sleator Remove this filter

and

  1. No Access

    Chapter and Conference Paper

    Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity

    We give offline algorithms for processing a sequence of 2- and 3-edg...

    Richard Peng, Bryce Sandlund, Daniel D. Sleator in Algorithms and Data Structures (2019)

  2. No Access

    Chapter and Conference Paper

    Skip-Splay: Toward Achieving the Unified Bound in the BST Model

    We present skip-splay, the first binary search tree algorithm known to have a running time that nearly achieves the unified bound. Skip-splay trees require only O(m lg lg n + UB(σ)) time to execute a query sequen...

    Jonathan C. Derryberry, Daniel D. Sleator in Algorithms and Data Structures (2009)

  3. No Access

    Article

    Randomized competitive algorithms for the list update problem

    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 tha...

    Nick Reingold, Jeffery Westbrook, Daniel D. Sleator in Algorithmica (1994)

  4. No Access

    Chapter and Conference Paper

    Data structures and terminating Petri nets

    Consider a collection of particles of various types, and a set of reactions that are allowed to take place among these particles. Each reaction is defined by an input linear combination of particle types, and ...

    Daniel D. Sleator in LATIN '92 (1992)

  5. No Access

    Article

    A strongly competitive randomized paging algorithm

    Thepaging problem is that of deciding which pages to keep in a memory ofk pages in order to minimize the number of page faults. We develop thepartitioning algorithm, a randomized on-line algorithm for the paging ...

    Lyle A. McGeoch, Daniel D. Sleator in Algorithmica (1991)

  6. No Access

    Article

    Competitive snoopy caching

    In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. Each cach...

    Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator in Algorithmica (1988)

  7. No Access

    Chapter

    Rotation Distance

    In this note we summarize our recent results on rotation distance, a distance measure on binary trees with computer science applications. Our main result is that the maximum rotation distance between any two n-no...

    Daniel D. Sleator, Robert E. Tarjan… in Open Problems in Communication and Computa… (1987)

  8. No Access

    Article

    The pairing heap: A new form of self-adjusting heap

    Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as ...

    Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, Robert E. Tarjan in Algorithmica (1986)