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

by Susanne Albers (Editor), Helmut Alt (Editor), Stefan Näher (Editor)

Overview

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.

Product Details

ISBN-13:	9783642034558
Publisher:	Springer Berlin Heidelberg
Publication date:	09/29/2009
Series:	Lecture Notes in Computer Science , #5760
Edition description:	2009
Pages:	439
Product dimensions:	6.00(w) x 9.30(h) x 0.70(d)

Table of Contents

I Models of Computation and Complexity

Building Mathematics-Based Software Systems to Advance Science and Create Knowledge Robert L. Constable 3

On Negations in Boolean Networks Norbert Blum 18

The Lovász Local Lemma and Satisfiability Heidi Gebauer Robin A. Moser Dominik Scheder Emo Welzl 30

Kolmogorov-Complexity Based on Infinite Computations Günter Hotz 55

Pervasive Theory of Memory Ulan Degenbaev Wolfgang J. Paul Norbert Schirmer 74

Introducing Quasirandomness to Computer Science Benjamin Doerr 99

II Sorting and Searching

Reflections on Optimal and Nearly Optimal Binary Search Trees J. Ian Munro 115

Some Results for Elementary Operations Athanasios K. Tsakalidis 121

Maintaining Ideally Distributed Random Search Trees without Extra Space Raimund Seidel 134

A Pictorial Description of Cole's Parallel Merge Sort Torben Hagerup 143

Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction Franco P. Preparata 158

III Combinatorial Optimization with Applications

Algorithms for Energy Saving Susanne Albers 173

Minimizing Average Flow-Time Naveen Garg 187

Integer Linear Programming in Computational Biology Ernst Althaus Gunnar W. Klau Oliver Kohlbacher Hans-Peter Lenhof Knut Reinert 199

Via Detours to I/O-Efficient Shortest Paths Ulrich Meyer 219

IV Computational Geometry and Geometric Graphs

The Computational Geometry of Comparing Shapes Helmut Alt 235

Finding Nearest Larger Neighbors: A Case Study in Algorithm Design and Analysis Tetsuo Asano Sergey Bereg David Kirkpatrick 249

Multi-core Implementations of Geometric Algorithms Stefan Näher Daniel Schmitt 261

The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension Michiel Smid 275

On Map Labeling with Leaders Michael Kaufmann 290

The Crossing Number of Graphs: Theory and Computation Petra Mutzel 305

V Algorithm Engineering, Exactness, and Robustness

Algorithm Engineering - An Attempt at a Definition Peter Sanders 321

Of What Use Is Floating-Point Arithmetic in Computational Geometry? Stefan Funke 341

Car or Public Transport-Two Worlds Hannah Bast 355

Is the World Linear? Rudolf Fleischer 368

In Praise of Numerical Computation Chee K. Yap 380

Much Ado about Zero Stefan Schirra 408

Polynomial Precise Interval Analysis Revisited Thomas Gawlitza Jérôme Leroux Jan Reineke Helmut Seidl Grégoire Sutre Reinhard Wilhelm 422

Author Index 439