Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Efficient Algorithms

Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday

  • Book
  • © 2009

Overview

Editors:
  1. Susanne Albers

    1. Institut für Informatik, Universität Freiburg, Freiburg, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Helmut Alt

    1. Institut für Informatik, Freie Universität Berlin, Berlin, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Stefan Näher

    1. Fachbereich IV - Informatik, Universität Trier, Trier, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 5760)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (28 chapters)

  1. Front Matter

    Download chapter PDF

  2. Models of Computation and Complexity

    1. Front Matter

      Pages 1-1
      Download chapter PDF

    2. Building Mathematics-Based Software Systems to Advance Science and Create Knowledge

      • Robert L. Constable
      Pages 3-17

    3. On Negations in Boolean Networks

      • Norbert Blum
      Pages 18-29

    4. The Lovász Local Lemma and Satisfiability

      • Heidi Gebauer, Robin A. Moser, Dominik Scheder, Emo Welzl
      Pages 30-54

    5. Kolmogorov-Complexity Based on Infinite Computations

      • Günter Hotz
      Pages 55-73

    6. Pervasive Theory of Memory

      • Ulan Degenbaev, Wolfgang J. Paul, Norbert Schirmer
      Pages 74-98

    7. Introducing Quasirandomness to Computer Science

      • Benjamin Doerr
      Pages 99-111

  3. Sorting and Searching

    1. Front Matter

      Pages 113-113
      Download chapter PDF

    2. Reflections on Optimal and Nearly Optimal Binary Search Trees

      • J. Ian Munro
      Pages 115-120

    3. Some Results for Elementary Operations

      • Athanasios K. Tsakalidis
      Pages 121-133

    4. Maintaining Ideally Distributed Random Search Trees without Extra Space

      • Raimund Seidel
      Pages 134-142

    5. A Pictorial Description of Cole’s Parallel Merge Sort

      • Torben Hagerup
      Pages 143-157

    6. Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction

      • Franco P. Preparata
      Pages 158-169

  4. Combinatorial Optimization with Applications

    1. Front Matter

      Pages 171-171
      Download chapter PDF

    2. Algorithms for Energy Saving

      • Susanne Albers
      Pages 173-186

    3. Minimizing Average Flow-Time

      • Naveen Garg
      Pages 187-198

    4. Integer Linear Programming in Computational Biology

      • Ernst Althaus, Gunnar W. Klau, Oliver Kohlbacher, Hans-Peter Lenhof, Knut Reinert
      Pages 199-218

    5. Via Detours to I/O-Efficient Shortest Paths

      • Ulrich Meyer
      Pages 219-232

  5. Computational Geometry and Geometric Graphs

    1. Front Matter

      Pages 233-233
      Download chapter PDF
Back to top

Keywords

About this book

This Festschrift volume, published in honor of Kurt Mehlhorn on the occasion of his 60th birthday, contains 28 papers written by his former Ph.D. students and colleagues as well as by his former Ph.D. advisor, Bob Constable.

The volume's title is a translation of the title of Kurt Mehlhorn's first book, "Effiziente Algorithmen", published by Teubner-Verlag in 1977. This Festschrift demonstrates how the field of algorithmics has developed and matured in the decades since then.

The papers included in this volume are organized in topical sections on models of computation and complexity; sorting and searching; combinatorial optimization with applications; computational geometry and geometric graphs; and algorithm engineering, exactness and robustness.

Editors and Affiliations

  • Institut für Informatik, Universität Freiburg, Freiburg, Germany

    Susanne Albers

  • Institut für Informatik, Freie Universität Berlin, Berlin, Germany

    Helmut Alt

  • Fachbereich IV - Informatik, Universität Trier, Trier, Germany

    Stefan Näher

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation