MPI-INF D1 Publications

Search the publication database

Your search returned the following 8 documents:

  1. Additive Spanners and (α, β)-Spanners
    Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, and Seth Pettie
    ACM Transactions on Algorithms 7 (1): 5:1-5:26, 2011
  2. Computing Approximate Matchings in External Memory, Streaming, Parallel, and Distributed Network Models
    Seth Pettie and Peter Sanders

  3. New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners
    Surender Baswana, Kavitha Telikepalli, Kurt Mehlhorn, and Seth Pettie
    In: Proceedings of the sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-05), Vancouver, Canada, 2005, 672-681

  4. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time
    Seth Pettie
    In: Algorithms and computation : 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, 2005, 964-973
  5. The complexity of implicit and space-efficient priority queues
    Christian Worm Mortensen and Seth Pettie
    In: Algorithms and data structures : 9th International Workshop, WADS 2005, Waterloo, Canada, 2005, 49-60
  6. Towards a final analysis of pairing heaps
    Seth Pettie
    In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), Pittsburgh, USA, 2005, 174-183
  7. A simpler linear time 2/3 - eps approximation for maximum weight matching
    Seth Pettie and Peter Sanders
    Information Processing Letters 91 (6): 271-276, 2004
    [PS: Download:]
  8. A Simpler Linear Time 2/3 - epsilon Approximation for Maximum Weight Matching
    Peter Sanders and Seth Pettie
    Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, MPI-I-2004-1-002, Research Report
    [PS: Download:]