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.
Author(s): Robert L. Constable (auth.), Susanne Albers, Helmut Alt, Stefan Näher (eds.)
Series: Lecture Notes in Computer Science 5760 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 439
Tags: Algorithm Analysis and Problem Complexity; Math Applications in Computer Science; Numeric Computing; Logics and Meanings of Programs; Discrete Mathematics in Computer Science; Software Engineering
Front Matter....Pages -
Front Matter....Pages 1-1
Building Mathematics-Based Software Systems to Advance Science and Create Knowledge....Pages 3-17
On Negations in Boolean Networks....Pages 18-29
The Lovász Local Lemma and Satisfiability....Pages 30-54
Kolmogorov-Complexity Based on Infinite Computations....Pages 55-73
Pervasive Theory of Memory....Pages 74-98
Introducing Quasirandomness to Computer Science....Pages 99-111
Front Matter....Pages 113-113
Reflections on Optimal and Nearly Optimal Binary Search Trees....Pages 115-120
Some Results for Elementary Operations....Pages 121-133
Maintaining Ideally Distributed Random Search Trees without Extra Space....Pages 134-142
A Pictorial Description of Cole’s Parallel Merge Sort....Pages 143-157
Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction....Pages 158-169
Front Matter....Pages 171-171
Algorithms for Energy Saving....Pages 173-186
Minimizing Average Flow-Time....Pages 187-198
Integer Linear Programming in Computational Biology....Pages 199-218
Via Detours to I/O-Efficient Shortest Paths....Pages 219-232
Front Matter....Pages 233-233
The Computational Geometry of Comparing Shapes....Pages 235-248
Finding Nearest Larger Neighbors....Pages 249-260
Multi-core Implementations of Geometric Algorithms....Pages 261-274
The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension....Pages 275-289
On Map Labeling with Leaders....Pages 290-304
Front Matter....Pages 233-233
The Crossing Number of Graphs: Theory and Computation....Pages 305-317
Front Matter....Pages 319-319
Algorithm Engineering – An Attempt at a Definition....Pages 321-340
Of What Use Is Floating-Point Arithmetic in Computational Geometry?....Pages 341-354
Car or Public Transport—Two Worlds....Pages 355-367
Is the World Linear?....Pages 368-379
In Praise of Numerical Computation....Pages 380-407
Much Ado about Zero....Pages 408-421
Polynomial Precise Interval Analysis Revisited....Pages 422-437
Back Matter....Pages -
