Kurt Mehlhorn

According to our database1, Kurt Mehlhorn
  • authored at least 386 papers between 1973 and 2017.
  • has a "Dijkstra number"2 of three.

Awards

ACM Fellow

ACM Fellow 1999, "For important contributions in complexity theory and in the design, analysis, and practice of combinatorial and geometric algorithms.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2017
Engineering DFS-Based Graph Algorithms.
CoRR, 2017

Approximating the Nash Social Welfare with Budget-Additive Valuations.
CoRR, 2017

Two Results on Slime Mold Computations.
CoRR, 2017

Certifying 3-Edge-Connectivity.
Algorithmica, 2017

Earning Limits in Fisher Markets with Spending-Constraint Utilities.
Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

2016
Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design.
Theory Comput. Syst., 2016

Computing real roots of real polynomials.
J. Symb. Comput., 2016

Improved balanced flow computation using parametric flow.
Inf. Process. Lett., 2016

A still simpler way of introducing interior-point method for linear programming.
Computer Science Review, 2016

The landscape of bounds for binary search trees.
CoRR, 2016

Computing Equilibria in Markets with Budget-Additive Utilities.
CoRR, 2016

An Integer Interior Point Method for Min-Cost Flow Using Arc Contractions and Deletions.
CoRR, 2016

Fair Matchings and Related Problems.
Algorithmica, 2016

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Opposition Frameworks.
Proceedings of the Logics in Artificial Intelligence - 15th European Conference, 2016

A Note On Spectral Clustering.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Computing Equilibria in Markets with Budget-Additive Utilities.
Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015
From approximate factorization to root isolation with application to cylindrical algebraic decomposition.
J. Symb. Comput., 2015

A combinatorial polynomial algorithm for the linear Arrow-Debreu market.
Inf. Comput., 2015

A Still Simpler Way of Introducing the Interior-Point Method for Linear Programming.
CoRR, 2015

A Note On Spectral Clustering.
CoRR, 2015

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.
CoRR, 2015

Improved Balanced Flow Computation Using Parametric Flow.
CoRR, 2015

Pattern-avoiding access in binary search trees.
CoRR, 2015

Greedy Is an Almost Optimal Deque.
CoRR, 2015

A Global Geometric View of Splaying.
CoRR, 2015

On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets.
Algorithmica, 2015

Greedy Is an Almost Optimal Deque.
Proceedings of the Algorithms and Data Structures - 14th International Symposium, 2015

Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design.
Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Pattern-Avoiding Access in Binary Search Trees.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Self-Adjusting Binary Search Trees: What Makes Them Tick?
Proceedings of the Algorithms - ESA 2015, 2015

On the Implementation of Combinatorial Algorithms for the Linear Exchange Market.
Proceedings of the Algorithms, Probability, Networks, and Games, 2015

Towards an open online repository of P. polycephalum networks and their corresponding graph representations.
Proceedings of the BICT 2015, 2015

P. polycephalum Can Compute Shortest Paths.
Proceedings of the BICT 2015, 2015

2014
On a Model of Virtual Address Translation.
ACM Journal of Experimental Algorithmics, 2014

A Framework for the Verification of Certifying Computations.
J. Autom. Reasoning, 2014

Equilibrium Computation (Dagstuhl Seminar 14342).
Dagstuhl Reports, 2014

Cache-Oblivious VAT-Algorithms.
CoRR, 2014

Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design.
CoRR, 2014

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms.
Algorithmica, 2014

Algorithms for Equilibrium Prices in Linear Market Models.
Proceedings of the Algorithms and Computation - 8th International Workshop, 2014

New Approximability Results for the Robust k-Median Problem.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

Verification of Certifying Computations through AutoCorres and Simpl.
Proceedings of the NASA Formal Methods - 6th International Symposium, NFM 2014, Houston, TX, USA, April 29, 2014

Algorithmen und Datenstrukturen - die Grundwerkzeuge.
eXamen.press, Springer, ISBN: 978-3-642-05471-6, 2014

2013
Every DFS Tree of a 3-Connected Graph Contains a Contractible Edge.
Journal of Graph Theory, 2013

Computational Geometry (Dagstuhl Seminar 13101).
Dagstuhl Reports, 2013

A Framework for the Verification of Certifying Computations
CoRR, 2013

On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets
CoRR, 2013

From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
CoRR, 2013

Computing Real Roots of Real Polynomials - An Efficient Method Based on Descartes' Rule of Signs and Newton Iteration.
CoRR, 2013

New Approximability Results for the Robust k-Median Problem.
CoRR, 2013

Certifying 3-Edge-Connectivity.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Physarum Computations (Invited talk).
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

From approximate factorization to root isolation.
Proceedings of the International Symposium on Symbolic and Algebraic Computation, 2013

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Fair Matchings and Related Problems.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets.
Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

The Query Complexity of Finding a Hidden Permutation.
Proceedings of the Space-Efficient Data Structures, 2013

The cost of address translation.
Proceedings of the 15th Meeting on Algorithm Engineering and Experiments, 2013

2012
Online graph exploration: New results on old and new algorithms.
Theor. Comput. Sci., 2012

The Deterministic and Randomized Query Complexity of a Simple Guessing Game.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Publication Culture in Computing Research (Dagstuhl Perspectives Workshop 12452).
Dagstuhl Reports, 2012

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
CoRR, 2012

The Cost of Address Translation
CoRR, 2012

Certifying 3-Edge-Connectivity
CoRR, 2012

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms
CoRR, 2012

Remarks on Category-Based Routing in Social Networks
CoRR, 2012

CGTA-Awards 2011.
Comput. Geom., 2012

An O(n+m) Certifying Triconnnectivity Algorithm for Hamiltonian Graphs.
Algorithmica, 2012

Physarum can compute shortest paths.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Counting Arbitrary Subgraphs in Data Streams.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
A deterministic algorithm for isolating real roots of a real polynomial.
J. Symb. Comput., 2011

Weisfeiler-Lehman Graph Kernels.
Journal of Machine Learning Research, 2011

An Introduction to Certifying Algorithms.
it - Information Technology, 2011

Computational Geometry (Dagstuhl Seminar 11111).
Dagstuhl Reports, 2011

Certifying algorithms.
Computer Science Review, 2011

Physarum Can Compute Shortest Paths
CoRR, 2011

A general approach to the analysis of controlled perturbation algorithms.
Comput. Geom., 2011

New Approximation Algorithms for Minimum Cycle Bases of Graphs.
Algorithmica, 2011

Guest Editorial: Selected Papers from European Symposium on Algorithms.
Algorithmica, 2011

The Physarum Computer.
Proceedings of the WALCOM: Algorithms and Computation - 5th International Workshop, 2011

Online Graph Exploration: New Results on Old and New Algorithms.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Approximate Counting of Cycles in Streams.
Proceedings of the Algorithms - ESA 2011, 2011

Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms.
Proceedings of the Algorithms - ESA 2011, 2011

Verification of Certifying Computations.
Proceedings of the Computer Aided Verification - 23rd International Conference, 2011

Multiplication of Long Integers - Faster than Long Multiplication.
Proceedings of the Algorithms Unplugged, 2011

2010
Additive spanners and (alpha, beta)-spanners.
ACM Trans. Algorithms, 2010

Arrangements on Parametric Surfaces I: General Framework and Infrastructure.
Mathematics in Computer Science, 2010

Faster algorithms for computing Hong's bound on absolute positiveness.
J. Symb. Comput., 2010

Editorial.
Comput. Geom., 2010

Assigning Papers to Referees.
Algorithmica, 2010

Reliable and Efficient Geometric Computing.
Proceedings of the Mathematical Software, 2010

Progress on Certifying Algorithms.
Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009
Minimum cycle bases: Faster and simpler.
ACM Trans. Algorithms, 2009

Efficient graphlet kernels for large graph comparison.
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, 2009

Cycle bases in graphs characterization, algorithms, complexity, and applications.
Computer Science Review, 2009

Note on the paper "K-vertex guarding simple polygons" [Computational Geometry 42 (4) (May 2009) 352-361].
Comput. Geom., 2009

A Separation Bound for Real Algebraic Expressions.
Algorithmica, 2009

Isolating real roots of real polynomials.
Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2009

Assigning Papers to Referees.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Breaking the O(m2n) Barrier for Minimum Cycle Bases.
Proceedings of the Algorithms, 2009

2008
Multiplikation langer Zahlen (schneller als in der Schule).
Proceedings of the Taschenbuch der Algorithmen, 2008

Faster Algorithms for Minimum Cycle Basis in Directed Graphs.
SIAM J. Comput., 2008

Classroom examples of robustness problems in geometric computations.
Comput. Geom., 2008

An [(O)\tilde](m2n)\tilde{O}(m^{2}n) Algorithm for Minimum Cycle Basis of Graphs.
Algorithmica, 2008

Algorithms and Data Structures: The Basic Toolbox.
Springer, ISBN: 978-3-540-77977-3, 2008

2007
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem.
ACM Trans. Algorithms, 2007

Popular Matchings.
SIAM J. Comput., 2007

Algorithms to Compute Minimum Cycle Basis in Directed Graphs.
Theory Comput. Syst., 2007

Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments.
Comput. Geom., 2007

Cycle bases of graphs and sampled manifolds.
Computer Aided Geometric Design, 2007

New Approximation Algorithms for Minimum Cycle Bases of Graphs.
Proceedings of the STACS 2007, 2007

Minimum Cycle Bases in Graphs Algorithms and Applications.
Proceedings of the Mathematical Foundations of Computer Science 2007, 2007

Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step.
Proceedings of the Algorithms, 2007

Matchings in Graphs Variations of the Problem.
Proceedings of the Combinatorial Optimization and Applications, 2007

2006
Rank-maximal matchings.
ACM Trans. Algorithms, 2006

Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs.
SIAM J. Comput., 2006

Matching Algorithms Are Fast in Sparse Random Graphs.
Theory Comput. Syst., 2006

New bounds for the Descartes method.
J. Symb. Comput., 2006

Implementing minimum cycle basis algorithms.
ACM Journal of Experimental Algorithmics, 2006

Polyline Fitting of Planar Points under Min-sum Criteria.
Int. J. Comput. Geometry Appl., 2006

Reliable Geometric Computing.
Proceedings of the Operations Research, 2006

Reply to "Backward Error Analysis ...".
Proceedings of the Computational Science and Its Applications, 2006

Reliable and Efficient Computational Geometry Via Controlled Perturbation.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Reliable and Efficient Geometric Computing.
Proceedings of the Algorithms, 2006

A Descartes Algorithms for Polynomials with Bit-Stream Coefficients.
Proceedings of the Reliable Implementation of Real Number Algorithms: Theory and Practice, 08.01., 2006

Reliable and Efficient Geometric Computing.
Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005
Structural filtering: a paradigm for efficient and exact geometric programs.
Comput. Geom., 2005

New bounds for the Descartes method.
ACM SIGSAM Bulletin, 2005

Implementing Minimum Cycle Basis Algorithms.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs.
Proceedings of the STACS 2005, 2005

Controlled perturbation for Delaunay triangulations.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

New constructions of (alpha, beta)-spanners and purely additive spanners.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Popular matchings.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Pareto Optimality in House Allocation Problems.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Towards Optimal Multiple Selection.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Minimum Cycle Bases and Surface Reconstruction.
Proceedings of the Graph Drawing, 13th International Symposium, 2005

EXACUS: Efficient and Exact Algorithms for Curves and Surfaces.
Proceedings of the Algorithms, 2005

A Descartes Algorithm for Polynomials with Bit-Stream Coefficients.
Proceedings of the Computer Algebra in Scientific Computing, 8th International Workshop, 2005

2004
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem.
Proceedings of the STACS 2004, 2004

Matching Algorithms Are Fast in Sparse Random Graphs.
Proceedings of the STACS 2004, 2004

Rank-maximal matchings.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Point containment in the integer hull of a polyhedron.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Polyline Fitting of Planar Points Under Min-sum Criteria.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Pareto Optimality in House Allocation Problems.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

A Faster Algorithm for Minimum Cycle Basis of Graphs.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Classroom Examples of Robustness Problems in Geometric Computations.
Proceedings of the Algorithms, 2004

04301 Abstracts Collection - Cache-Oblivious and Cache-Aware Algorithms.
Proceedings of the Cache-Oblivious and Cache-Aware Algorithms, 18.07. - 23.07.2004, 2004

2003
An efficient graph algorithm for dominance constraints.
J. Algorithms, 2003

Optimal search for rationals.
Inf. Process. Lett., 2003

Infimaximal Frames: A Technique for Making Lines Look Like Segments.
Int. J. Comput. Geometry Appl., 2003

Scanning Multiple Sequences Via Cache Memory.
Algorithmica, 2003

A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms.
Algorithmica, 2003

The Reliable Algorithmic Software Challenge RASC.
Proceedings of the Experimental and Efficient Algorithms, Second International Workshop, 2003

Certifying algorithms for recognizing interval graphs and permutation graphs.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Certifying and repairing solutions to large LPs how good are LP-solvers?
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Smoothed Analysis of Three Combinatorial Problems.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation.
Proceedings of the Algorithms, 2003

The Reliable Algorithmic Software Challenge RASC.
Proceedings of the Computer Science in Perspective, Essays Dedicated to Thomas Ottmann, 2003

2002
Implementation of O(n m log n) Weighted Matchings in General Graphs: The Power of Data Structures.
ACM Journal of Experimental Algorithmics, 2002

All-pairs shortest-paths computation in the presence of negative cycles.
Inf. Process. Lett., 2002

LOOK: A Lazy Object-Oriented Kernel design for geometric computation.
Comput. Geom., 2002

External-Memory Breadth-First Search with Sublinear I/O.
Proceedings of the Algorithms, 2002

A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons.
Proceedings of the Algorithms, 2002

SCIL - Symbolic Constraints in Integer Linear Programming.
Proceedings of the Algorithms, 2002

2001
Traveling Salesman-Based Curve Reconstruction in Polynomial Time.
SIAM J. Comput., 2001

Furthest Site Abstract Voronoi Diagrams.
Int. J. Comput. Geometry Appl., 2001

Randomized External-Memory Algorithms for Line Segment Intersection and Other Geometric Problems.
Int. J. Comput. Geometry Appl., 2001

An efficient algorithm for the configuration problem of dominance graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Exact geometric computation.
Proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01), 2001

A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms.
Proceedings of the Algorithms, 2001

A Separation Bound for Real Algebraic Expressions.
Proceedings of the Algorithms, 2001

From Algorithm to Program to Software Library.
Proceedings of the Informatics - 10 Years Back. 10 Years Ahead., 2001

CNOP - A Package for Constrained Network Optimization.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

Exact Computation with leda_real - Theory and geometric Applications.
Proceedings of the Symbolic Algebraic Methods and Verification Methods, 2001

2000
Average-case complexity of shortest-paths problems in the vertex-potential model.
Random Struct. Algorithms, 2000

A polyhedral approach to sequence alignment problems.
Discrete Applied Mathematics, 2000

Editorial.
Comput. Geom., 2000

Curve reconstruction: Connecting dots with good reason.
Comput. Geom., 2000

A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals.
Algorithmica, 2000

Implementation of O (nm log n) Weighted Matchings in General Graphs. The Power of Data Structures.
Proceedings of the Algorithm Engineering, 2000

TSP-based curve reconstruction in polynomial time.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Constraint Programming and Graph Algorithms.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Resource Constrained Shortest Paths.
Proceedings of the Algorithms, 2000

Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint.
Proceedings of the Principles and Practice of Constraint Programming, 2000

Look - a Lazy Object-Oriented Kernel for geometric computation.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000

A Polynomial-Time Fragment of Dominance Constraints.
Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics, 2000

1999
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow.
Inf. Process. Lett., 1999

A Correctness Certificate for the Stoer-Wagner Min-Cut Algorithm.
Inf. Process. Lett., 1999

Editorial.
Comput. Geom., 1999

Checking geometric programs or verification of geometric structures.
Comput. Geom., 1999

Ten Years of LEDA Some Thoughts (Abstract).
Proceedings of the Algorithm Engineering, 1999

LEDA-SM Extending LEDA to Secondary Memory.
Proceedings of the Algorithm Engineering, 1999

Checking Priority Queues.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

The Engineering of Some Bipartite Matching Programs.
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

The Engineering of some Bipartite Matching Programs.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1999

Curve Reconstruction: Connecting Dots with Good Reason.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Efficient Exact Geometric Computation Made Easy.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999

Structural filtering: A paradigm for efficient and exact geometric programs.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

LEDA: A Platform for Combinatorial and Geometric Computing.
Cambridge University Press, ISBN: 0-521-56329-1, 1999

1998
Maximum Network Flow with Floating Point Arithmetic.
Inf. Process. Lett., 1998

A computational basis for higher-dimensional computational geometry and applications.
Comput. Geom., 1998

From Algorithms to Working Programs: On the Use of Program Checking in LEDA.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

A Parallelization of Dijkstra's Shortest Path Algorithm.
Proceedings of the Mathematical Foundations of Computer Science 1998, 1998

From Algorithms to Working Programs on the Use of Program Checking in LEDA.
Proceedings of the Fundamentals - Foundations of Computer Science, 1998

I/O-optimal computation of segment intersections.
Proceedings of the External Memory Algorithms, 1998

Randomized External-Memory Algorithms for Some Geometric Problems.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997
On the all-pairs shortest-path algorithm of Moffat and Takaoka.
Random Struct. Algorithms, 1997

Maintaining Dynamic Sequences under Equality Tests in Polylogarithmic Time.
Algorithmica, 1997

Runtime Prediction of Real Programs on Real Machines.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Square Roots.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A branch-and-cut algorithm for multiple sequence alignment.
Proceedings of the First Annual International Conference on Research in Computational Molecular Biology, 1997

Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

The LEDA Platform of Combinatorial and Geometric Computing.
Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

A Complete Roundness Classification Procedure.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

A Computational Basis for Higher-Dimensional Computational Geometry and Applications.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997

1996
An o(n³)-Time Algorithm Maximum-Flow Algorithm.
SIAM J. Comput., 1996

On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm.
Algorithmica, 1996

Algorithms for Dense Graphs and Networks on the Random Access Computer.
Algorithmica, 1996

A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica, 1996

Position Paper for Panel Discussion.
Proceedings of the Applied Computational Geormetry, 1996

The LEDA Platform for Combinatorial and Geometric Computing.
Proceedings of the Beherrschung von Informationssystemen, 1996

Checking Geometric Programs or Verification of Geometric Structures.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996

1995
A Communication-Randomness Tradeoff for Two-Processor Systems
Inf. Comput., February, 1995

Guest Editor's Foreword.
Discrete & Computational Geometry, 1995

LEDA: A Platform for Combinatorial and Geometric Computing.
Commun. ACM, 1995

Lower Bounds for Set Intersection Queries.
Algorithmica, 1995

Experiences with the Implementation of Geometric Algorithms (Abstract).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka.
Proceedings of the Algorithms, 1995

Exact Geometric Computation in LEDA.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

1994
A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs.
SIAM J. Comput., 1994

Dynamic Perfect Hashing: Upper and Lower Bounds.
SIAM J. Comput., 1994

Dynamic Point Location in General Subdivisions.
J. Algorithms, 1994

A Lower Bound for Area-Universal Graphs.
Inf. Process. Lett., 1994

Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

On Degeneracy in Geometric Computations.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

The Implementation of Geometric Algorithms.
Proceedings of the Technology and Foundations - Information Processing '94, Volume 1, Proceedings of the IFIP 13th World Computer Congress, Hamburg, Germany, 28 August, 1994

How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results.
Proceedings of the Algorithms, 1994

1993
Dynamic Interpolation Search.
J. ACM, 1993

Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection.
Comput. Geom., 1993

Randomized Incremental Construction of Abstract Voronoi Diagrams.
Comput. Geom., 1993

Four Results on Randomized Incremental Constructions.
Comput. Geom., 1993

A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron.
Proceedings of the Algorithms and Data Structures, Third Workshop, 1993

Exact Algorithms for a Geometric Packing Problem (Extended Abstract).
Proceedings of the STACS 93, 1993

Lower Bounds for Set Intersection Queries.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Maintaining Discrete Probability Distributions Optimally.
Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Searching, Sorting and Randomised Algorithms for Central Elements and Ideal Counting in Posets.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1993

Komplexitätstheorie und Algorithmik.
Proceedings of the Informatik: Grundlagen - Amwendungen, 1993

1992
k versus k+1 Index Registers and Modifiable versus Non-modifiable Programs
Inf. Comput., November, 1992

On local routing of two-terminal nets.
J. Comb. Theory, Ser. B, 1992

A Lower Bound for the Nondeterministic Space Complexity of Context-Free Recognition.
Inf. Process. Lett., 1992

Simultaneous Inner and Outer Approximation of Shapes.
Algorithmica, 1992

Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures.
Algorithmica, 1992

Four Results on Randomized Incremental Constructions.
Proceedings of the STACS 92, 1992

Tail Estimates for the Space Complexity of Randomized Incremental Algorithms.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Dynamic Point Location in General Subdivisions.
Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Algorithm Design and Software Libraries: Recent Developments in the LEDA Project.
Proceedings of the Algorithms, Software, Architecture, 1992

Recent Developments in Algorithms for the Maximum-Flow Problem (Abstract).
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

Selected Topics from Computational Geometry, Data Structures and Motion Planning.
Proceedings of the Data Structures and Efficient Algorithms, 1992

1991
Constructive Whitney-Graustein Theorem: Or How to Untangle Closed Planar Curves.
SIAM J. Comput., 1991

Computing a Maximum Cardinality Matching in a Bipartite Graph in Time O(^1.5 sqrt m/log n).
Inf. Process. Lett., 1991

On the Construction of Abstract Voronoi Diagrams.
Discrete & Computational Geometry, 1991

1990
Faster Algorithms for the Shortest Path Problem
J. ACM, April, 1990

Compaction on the torus [VLSI layout].
IEEE Trans. on CAD of Integrated Circuits and Systems, 1990

A faster compaction algorithm with automatic jog insertion.
IEEE Trans. on CAD of Integrated Circuits and Systems, 1990

On the Complexity of a Game Related to the Dictionary Problem.
SIAM J. Comput., 1990

Hidden Line Elimination for Isooriented Rectangels.
Inf. Process. Lett., 1990

Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space.
Inf. Process. Lett., 1990

Dynamic Deferred Data Structuring.
Inf. Process. Lett., 1990

Dynamic Fractional Cascading.
Algorithmica, 1990

A Time-Randomness Tradeoff for Communication Complexity.
Proceedings of the Distributed Algorithms, 4th International Workshop, 1990

On the Construction of Abstract Voronoi Diagrams.
Proceedings of the STACS 90, 1990

On the Construction of Abstract Voronoi Diagrams, II.
Proceedings of the Algorithms, 1990

LEDA: A Library of Efficient Data Types and Algorithms.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

Can A Maximum Flow be Computed on o(nm) Time?
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

LEDA - A Library of Efficient Data Types and Algorithms.
Proceedings of the GI, 1990

On Simultaneous Inner and Outer Approximation of Shapes.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures.
Proceedings of the Sixth Annual Symposium on Computational Geometry, 1990

Data Structures.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
AT²-Optimal Galois Field Multiplier for VLSI.
IEEE Trans. Computers, 1989

LEDA: A Library of Efficient Data Types and Algorithms.
Proceedings of the Mathematical Foundations of Computer Science 1989, 1989

Two Versus One Index Register and Modifiable Versus Non-modifiable Programs.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

On the Complexity of a Game Related to the Dictionary Problem
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Foundations of Programming Languages
John Wiley, ISBN: 0-471-92139-4, 1989

1988
A Lower Bound on the Complexity of the Union-Split-Find Problem.
SIAM J. Comput., 1988

A Faster Approximation Algorithm for the Steiner Problem in Graphs.
Inf. Process. Lett., 1988

Parallel Algorithms for Computing Maximal Independent Sets in Trees and for Updating Minimum Spanning Trees.
Inf. Process. Lett., 1988

Congruence, Similarity, and Symmetries of Geometric Objects.
Discrete & Computational Geometry, 1988

Upper and Lower Bounds for the Dictionary Problem (Abstract).
Proceedings of the SWAT 88, 1988

Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves.
Proceedings of the Automata, Languages and Programming, 15th International Colloquium, 1988

SFB 124: VLSI-Entwurfsmethoden und Parallelität.
Proceedings of the GI, 1988

Dynamic Perfect Hashing: Upper and Lower Bounds
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On Continuous Homotopic One Layer Routing.
Proceedings of the Fourth Annual Symposium on Computational Geometry, 1988

On Continuous Homotopic One Layer Routing.
Proceedings of the Computational Geometry and its Applications, 1988

Compaction on the Torus.
Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987
Area-Time Optimal Division for T=Omega((log n)^1+ epsilon)
Inf. Comput., March, 1987

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones.
SIAM J. Comput., 1987

A log log n Data Structure for Three-Sided Range Queries.
Inf. Process. Lett., 1987

On Local Routing of Two-Terminal Nets.
Proceedings of the STACS 87, 1987

Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones.
Proceedings of the Parallel Algorithms and Architectures, 1987

A Lower Bound for the Complexity of the Union-Split-Find Problem.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

Congruence, Similarity, and Symmetries of Geometric Objects.
Proceedings of the Third Annual Symposium on Computational Geometry, 1987

1986
An Amortized Analysis of Insertions into AVL-Trees.
SIAM J. Comput., 1986

Routing Through a Generalized Switchbox.
J. Algorithms, 1986

Routing through a rectangle.
J. ACM, 1986

Über Verdrahtungsalgorithmen.
Informatik Spektrum, 1986

Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees
Information and Control, 1986

On BF-orderable graphs.
Discrete Applied Mathematics, 1986

Channel Routing in Knock-Knee Mode: Simplified Algorithms and Proofs.
Algorithmica, 1986

Algorithms for Routing in Planar Graphs.
Acta Inf., 1986

Area-time Optimal Division for T=Omega(log n)1+epsilon
Proceedings of the STACS 86, 1986

Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones.
Proceedings of the Mathematical Foundations of Computer Science 1986, 1986

AT2-Optimal Galois Field Multiplier for VLSI.
Proceedings of the VLSI Algorithms and Architectures, 1986

Grundlagen der Programmiersprachen
Teubner, ISBN: 3-519-02254-0, 1986

1985
Searching Semisorted Tables.
SIAM J. Comput., 1985

A Fast Algorithm for Renaming a Set of Clauses as a Horn Set.
Inf. Process. Lett., 1985

Fast Triangulation of the Plane with Respect to Simple Polygons
Information and Control, 1985

Dynamic Interpolation Search.
Proceedings of the Automata, 1985

Routing Through a Generalized Switchbox.
Proceedings of the Automata, 1985

Intersecting two polyhedra one of which is convex.
Proceedings of the Fundamentals of Computation Theory, 1985

Sorting Jordan sequences in linear time.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

Dynamization of geometric data structures.
Proceedings of the First Annual Symposium on Computational Geometry, 1985

1984
Partial Match Retrieval in Implicit Data Structures.
Inf. Process. Lett., 1984

AT2-optimal VLSI integer division and integer square rooting.
Integration, 1984

Randomized and Deterministic Simulations of PRAMs by Parallel Machines with Restricted Granularity of Parallel Memories.
Acta Inf., 1984

Space Sweep Solves Intersection of Convex Polyhedra.
Acta Inf., 1984

Area-Time Optimal VLSI Integer Multiplier with Minimum Computation Time.
Proceedings of the Automata, 1984

Über Verdrahtungsalgorithmen.
Proceedings of the Fachgespräche auf der 14. GI-Jahrestagung, 1984

On Optimal VLSI-Circuits for the Basic Arithmetic Functions.
Proceedings of the CAAP'84, 1984

Data Structures and Algorithms 3: Multi-dimensional Searching and Computational Geometry
EATCS Monographs on Theoretical Computer Science 3, Springer, ISBN: 978-3-642-69900-9, 1984

Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness
EATCS Monographs on Theoretical Computer Science 2, Springer, ISBN: 978-3-642-69897-2, 1984

Data Structures and Algorithms 1: Sorting and Searching
EATCS Monographs on Theoretical Computer Science 1, Springer, ISBN: 978-3-642-69672-5, 1984

1983
Cost Trade-offs in Graph Embeddings, with Applications
J. ACM, October, 1983

Area-Time Optimal VLSI Integer Multiplier with Minimum Computation Time
Information and Control, 1983

The Recognition of Deterministic CFL's in Small Time and Space
Information and Control, 1983

A Single Shortest Path Algorithm for Graphs with Separators.
Proceedings of the Fundamentals of Computation Theory, 1983

Fast Triangulation of Simple Polygons.
Proceedings of the Fundamentals of Computation Theory, 1983

1982
A Partial Analysis of Height-Balanced Trees Under Random Insertions and Deletions.
SIAM J. Comput., 1982

A Probabilistic Algorithm for Vertex Connectivity of Graphs.
Inf. Process. Lett., 1982

The Theory of Fringe Analysis and Its Application to 2-3 Trees and B-Trees
Information and Control, 1982

A New Data Structure for Representing Sorted Lists.
Acta Inf., 1982

Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

On the Program Size of Perfect and Universal Hash Functions
Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981
Lower Bounds on the Efficiency of Transforming Static Data sSructures into Dynamic Structures.
Mathematical Systems Theory, 1981

Arbitrary Weight Changes in Dynamic Trees.
ITA, 1981

Optimal Dynamization of Decomposable Searching Problems.
Inf. Process. Lett., 1981

Lower Bounds on the Efficiency of Transforming Static Data Structures into Dynamic Structures.
Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG '81), 1981

Robust Balancing in B-Trees.
Proceedings of the Theoretical Computer Science, 1981

Partial Match Retrieval in Implicit Data Structures.
Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

Cost Tradeoffs in Graph Embeddings, with Applications (Preliminary Version).
Proceedings of the Automata, 1981

1980
An efficient algorithm for constructing nearly optimal prefix codes.
IEEE Trans. Information Theory, 1980

On the Average Number of Rebalancing Operations in Weight-Balanced Trees.
Theor. Comput. Sci., 1980

Codes: Unequal Probabilities, Unequal Letter Cost.
J. ACM, 1980

Binary Search Trees: Average and Worst Case Behavior.
Elektronische Informationsverarbeitung und Kybernetik, 1980

A New Data Structure for Representing Sorted Lists.
Proceedings of the Graphtheoretic Concepts in Computer Science, 1980

Pebbling Moutain Ranges and its Application of DCFL-Recognition.
Proceedings of the Automata, 1980

1979
Parsing Macro Grammars Top Down
Information and Control, February, 1979

Dynamic Binary Search.
SIAM J. Comput., 1979

Complexity arguments in algebraic language theory.
ITA, 1979

Some Remarks on Boolean Sums.
Acta Inf., 1979

Sorting Presorted Files.
Proceedings of the Theoretical Computer Science, 1979

Mittlere Anzahl von Rebalancierungsoperationen in gewichtsbalancierten Bäumen.
Proceedings of the Theoretical Computer Science, 1979

Some Remarks on Boolean Sums.
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

Searching, Sorting and Information Theory.
Proceedings of the Mathematical Foundations of Computer Science 1979, 1979

Konzepte der Komplexitätstheorie illustriert am Beispiel des Sortierens.
Proceedings of the GI - 9. Jahrestagung, Bonn, 1.-5. Oktober 1979, Proceedings, 1979

1978
Effiziente Algorithmen: Ein Beispiel.
Informatik Spektrum, 1978

Codes: Unequal Probabilities, Unequal Letter Costs (Extended Abstract).
Proceedings of the Automata, 1978

1977
A Best Possible Bound for the Weighted Path Length of Binary Search Trees.
SIAM J. Comput., 1977

Van Wijngaarden Grammars and Space Complexity Classs EXSPACE.
Acta Inf., 1977

Dynamic Binary Search.
Proceedings of the Automata, 1977

Effiziente Algorithmen
Teubner, ISBN: 3-519-02343-1, 1977

1976
Polynomial and Abstract Subrecursive Classes.
J. Comput. Syst. Sci., 1976

Bracket-Languages are Recognizable in Logarithmic Space.
Inf. Process. Lett., 1976

An Improved Lower Bound on the Formula Complexity of Context-free Recognition.
Elektronische Informationsverarbeitung und Kybernetik, 1976

Monotone switching circuits and boolean matrix product.
Computing, 1976

Lower Bounds for the Space Complexity of Context-Free Recognition.
ICALP, 1976

Top Down Parsing of Macro Grammars.
Proceedings of the GI - 6. Jahrestagung, Stuttgart, 29. September, 1976

Binary Search Trees: Average and Worst Case Behavior.
Proceedings of the GI - 6. Jahrestagung, Stuttgart, 29. September, 1976

1975
Nearly Optimal Binary Search Trees.
Acta Inf., 1975

Monotone Switching Circuits and Boolean Matrix Product.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

Best possible bounds for the weighted path length of optimum binary search trees.
Proceedings of the Automata Theory and Formal Languages, 1975

1974
Polynomial and Abstract Subrecursive Classes
Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30, 1974

The "Almost All" Theory of Subrecursive Degrees is Decidable.
Proceedings of the Automata, Languages and Programming, 2nd Colloquium, University of Saarbrücken, July 29, 1974

1973
On the Size of Sets of Computable Functions
Proceedings of the 14th Annual Symposium on Switching and Automata Theory, 1973


  Loading...