Abstract New Constructions of (α, β)-Spanners and Purely Additive Spanners ∗ (2009)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u, v: δH(u, v) ≤ αδG(u, v) + β, where δG is the...
Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Michael Seel
Abstract. We describe a data structure for three-dimensional Nef complexes, al-gorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were...
Kurt Mehlhorn, Wolfgang Rulling
Abstract-In this paper we introduce a general framework for com-paction on a torus. This problem comes up whenever an array of iden-tical cells has to be compacted. We instantiate our framework with...
Abstract Popular Matchings (2008)
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly involving...
der Universität des Saarlandes von (2008)
Andreas Crauser, Professor Dr, Kurt Mehlhorn, Mpi Für Informatik, Deutsche Kurzzusammenfassung
Die zu verarbeitenden Datenmengen sind in den letzten Jahren dramatisch gestiegen, so daß Externspeicher (in Form von Festplatten) eingesetzt wird, um die Datenmengen zu speichern. Algorithmen und...
Robert W. Irving Rank-Maximal Matchings (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set ¡ of applicants ranks a subset of a set of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
New Constructions of ¡ β ¢ α-Spanners and Purely Spanners£ Additive (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An ¦ α § β ¨-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u § v: δH ¦ u § v¨� © αδG ¦ u § v¨� �...
Efficient Graphlet Kernels for Large Graph Comparison (2008)
Shervashidze, Nino, Vishwanathan, S.V.N., Petri, Tobias H., Mehlhorn, Kurt, Borgwardt, Karsten M.
State-of-the-art graph kernels do not scale to large graphs with hundreds of nodes and thousands of edges. In this article we attempt to rectify this situation. We compare graphs by counting common...
Efficient Graphlet Kernels for Large Graph Comparison (2008)
Shervashidze, Nino, Vishwanathan, S V N, Petri, Tobias, Mehlhorn, Kurt, Borgwardt, Karsten
State-of-the-art graph kernels do not scale to large graphs with hundreds of nodes and thousands of edges. In this article we propose to compare graphs by counting common {\it graphlets}, \ie...
An (O)over-tilde (m(2)n) Algorithm for Minimum Cycle Basis of Graphs (2008)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E
We consider the problem of computing a minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices. In this problem, a {0,1} incidence vector is associated...
Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model...
Computer Algorithms. Addison-Wesley, 1974. (2008)
Milton Abramowitz, Irene A. Stegun, Leonard M. Adleman, Carl Pomerance, ...
numbers from composite numbers. Annals of Mathematics, 117:173–206, 1983. [4] Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of...
Additive Spanners and (α, β)-Spanners ∗ (2008)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a...
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 We show how to compute and maintain the two-dimensional arrangement on a quadric that is induced by...
Minimum Cycle Bases: Faster and Simpler (2008)
Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} ({−1, 0,...
An Õ(m2 n) algorithm for Minimum Cycle Basis of graphs ∗ (2008)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch
We consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The input to this problem is an undirected graph whose edges have non-negative weights. In this...
Approximability of Cycle Covers and Smoothed Analysis of Binary Search Trees (2008)
Bodo Manthey, Zur Erlangung Der, Bodo Manthey, Berichterstatter Prof, Dr. Rüdiger Reischuk, ...
the years. I also thank the current and former members of the Institut für Theoretische Informatik at the Universität zu Lübeck for many valuable discussions, not only about computer science. In...
Minimum Cycle Bases in Graphs Algorithms and Applications (2008)
A cycle basis of a graph is a family of cycles which spans all cycles of the graph. In an undirected graph, a cycle is simply a set of edges with respect to which every vertex has even degree. We...
ii Datum des Kolloquiums: 21.10.2002 (2008)
Ulrich Meyer, Dekan Prof, Gutachter Prof, Dr. Kurt Mehlhorn, Prof Dr, ...
Abstract. We study the performance of algorithms for the Single-Source Shortest-Paths (SSSP) problem on graphs with nodes ¡ and edges with nonnegative random weights. All previously known SSSP...
Federal Republic of Germany (2008)
Helmut Alt, Rudolf Fleischer, Michael Kaufmann, Kurt Mehlhorn, Stefan Schirra, Christian Uhrig, ...
Abstract: We study rigid motions of a rectangle amidst polygonal obstacles. The best known algorithms for this problem have running time f~(n 2) where n is the number of obstacle corners. We...
Abstract Point Containment in the Integer Hull of a Polyhedron 1 (2008)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most ϕ bits can be solved in time O(m + ϕ) in the...
158 Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs (2008)
Dieter Kratsch, Ross M. Mcconnell, Kurt Mehlhorn, Jeremy P. Spinrad
A certifying algorithm for a decision problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not...
Abstract: POLYNOMIAL AND ABSTRACT SUBRECURSIVE CLASSES* (2008)
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the...
der Universität des Saarlandes (2008)
Roman Dementiev, Prof Dr. -ing, Gerhard Weikum, Prof Dr. -ing, Gerhard Weikum, Prof Dr, ...
In recent years, the development of theoretically I/O-efficient algorithms and data structures has received considerable attention. However, much less has been done to evaluate their performance, in...
Smoothed Analysis of Three Combinatorial Problems ⋆ (2008)
Cyril B, René Beier, Kurt Mehlhorn
Abstract. Smoothed analysis combines elements over worst-case and average case analysis. For an instance x, the smoothed complexity is the average complexity of an instance obtained from x by a...
ii Datum des Kolloquiums: 21.10.2002 (2008)
Ulrich Meyer, Dekan Prof, Gutachter Prof, Dr. Kurt Mehlhorn, Prof Dr, ...
Abstract. We study the performance of algorithms for the Single-Source Shortest-Paths (SSSP) problem on graphs withÒnodes andÑedges with nonnegative random weights. All previously known SSSP...
Kurt Mehlhorn, Athanasios Tsakalidis
Abstract. A new data structure called interpolation search tree (1ST) is presented which supports interpolation search and insertions and deletions. Amortized insertion and deletion cost is O(log n)....
LEDA A Library of Efficient Data Types and Algorithms * (2008)
LEDA is a library of efficient data types and algorithms. At present, its strength is graph algorithms and related data structures. The computational geometry part is evolving. The main features of...
Minimum Cycle Bases: Faster and Simpler (2008)
Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing exact or approximate minimum cycle bases of an undirected (or directed) edge-weighted graph G with m edges and n vertices. In this problem, a {0, 1} ({−1, 0,...
Abstract Certifying and Repairing Solutions to Large LPs (2008)
Marcel Dhiflaoui, Stefan Funke, Kurt Mehlhorn, Michael Seel, Elmar Schömer, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
On the All-Pairs Shortest Path Algorithm (2008)
Of Moffat, Kurt Mehlhorn, Volker Priebe
Abstract. We review how to solve the all-pairs shortest path problem in a non-negatively weighted digraph with n vertices in expected time O(n 2 log n). This bound is shown to hold with high...
Geometric Computing with CGAL and LEDA (2008)
Abstract. LEDA and CGAL are platforms for combinatorial and geometric computing. We discuss the use of LEDA and CGAL for geometric computing and show that they provide a unique framework for exact,...
Universit~t des Saarlandes (2008)
Scott Huddleston, Kurt Mehlhorn
Robust balancing is a technique for maintaining generalized B-trees with a cumulative rebalancing cost that is asymptotically linear. It is especially significant in conjunction with fingers, which...
Certifying and Repairing Solutions to Large LPs - How Good are LP-solvers? (2008)
Marcel Dhiflaoui, Carsten Kwappik, Stefan Funke, Kurt Mehlhorn, Michael Seel, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
External-Memory Breadth-First Search with Sublinear I/O (2008)
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires (n...
A Faster Deterministic Algorithm for Minimum Cycle Basis in Directed Graphs (2008)
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn, Kavitha Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
SCIL - Symbolic Constraints in Integer Linear Programming (2008)
Ernst Althaus, Alexander Bockmayr, Matthias Elf, Michael Jünger, Thomas Kasper, Kurt Mehlhorn
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
Classroom examples of robustness problems in geometric computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause...
Classroom examples of robustness problems in geometric computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause...
An O˜ (m2n) Algorithm for Minimum Cycle Basis of Graphs (2008)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrions, Paluch, Katarzyna E.
Classroom Examples of Robustness Problems in Geometric Computations (2008)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
Faster Algorithms for Minimum Cycle Basis in Directed Graphs (2008)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph $G$ whose edges have nonnegative weights. A cycle in this graph is...
Lower Bounds, Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Fur Informatik, ...
The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a...
Kurt Mehlhorn, Christian Uhrig
1. Min-cuts in undirected graphs. Let G = (V; E) be an undirected graph (self-loops and parallel edges are allowed) and let w: E!!0 be a non-negative weight function on the edges of G. A cut C of G...
Kurt Mehlhorn, Kurt Mehlhorn, Stefan Schirra, Stefan Schirra
Partially supported by ESPRIT project 28155 (GALIA). Work done while the second author was at Max-Planck-Institut fur Informatik. We prove a separation bound for a large class of algebraic...
Sublinear I/o, Kurt Mehlhorn, Ulrich Meyer
Abstract. Breadth-first search (BFS) is a basic graph exploration technique. We give the first external memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm...
zur Erlangung des Grades (2007)
Volker Priebe, Dekan Prof, Dr. Rainer Schulze-pillot-ziemen, Gutachter Prof, Dr. Kurt Mehlhorn, ...
ii Abstract. We study both upper and lower bounds on the average-case complexity of shortest-paths algorithms. It is proved that the all-pairs shortest-paths problem on n-vertex networks can be...
An Ecient Algorithm for the Conguration Problem of Dominance Graphs (2007)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. The satisability problem of dominance constraints is...
Colin Cooper, Kurt Mehlhorn, Volker Priebe
complexity of shortest-paths problems in the
Veri ed Result Checkers (2007)
The programs in LEDA have reached a very high level of reliability. In fact, I claim that all major algorithms and data structures are correct. We have reached the current level of reliability...
Certifying and Repairing Solutions to Large LPs - How Good are LP-solvers? (2007)
Marcel Dhiflaoui, Carsten Kwappik, Stefan Funke, Kurt Mehlhorn, Michael Seel, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,0,1}...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. In this problem a {-1,0,1}...
Abraham, David J, Irving, Robert W, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving...
Abraham, David J, Irving, Robert W, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly involving...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
We introduce a general framework for processing a set of curves defined on a continuous two-dimensional parametric surface, while sweeping the parameter space. We can handle planes, cylinders,...
Pavel Emeliyanenko, Erstgutachter First Examiner, Prof Dr, Kurt Mehlhorn, Mpi Informatik Saarbrücken, ...
First of all I would like to thank Prof. Dr. Kurt Mehlhorn, my supervising professor at Saarland University, for offering me this stimulating topic as well as Algorithm Engineering course that...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, Ron Wein
Abstract. We introduce a general framework for sweeping a set of curves embedded on a two-dimensional parametric surface. We can handle planes, cylinders, spheres, tori, and surfaces homeomorphic to...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also...
Engineering DFS-Based Graph Algorithms (2007)
Kurt Mehlhorn, Stefan Näher, Peter S
Depth-first search (DFS) is the basis for many efficient graph algorithms. We introduce general techniques for efficient implementations of DFS-based graph algorithms and exemplify them on three...
New approximation algorithms for minimum cycle bases of graphs (2007)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
Sweeping and maintaining two-dimensional arrangements on surfaces: A first step (2007)
Berberich, Eric, Fogel, Efi, Halperin, Dan, Mehlhorn, Kurt, Wein, Ron
Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna E.
Sweeping and maintaining two-dimensional arrangements on quadrics (2007)
Berberich, Eric, Fogel, Efi, Halperin, Dan, Mehlhorn, Kurt, Wein, Ron
Implementing Minimum Cycle Basis Algorithms (2007)
Mehlhorn, Kurt, Michail, Dimitrios
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3...
Cycle Bases of Graphs and Sampled Manifolds (2007)
Gotsman, Craig, Kaligosi, Kanela, Mehlhorn, Kurt, Michail, Dimitrios, Pyrga, Evangelia
New Approximation Algorithms for Minimum Cycle Bases of Graphs (2007)
Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios
We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Kavitha, Telikepalli, Mehlhorn, Kurt
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Michael Kerber, Erstgutachter First Examiner, Prof Dr, Kurt Mehlhorn, Zweitgutachterin Second Examiner, ...
The following persons contributed to the success of this work. I want to thank them all for their support during the last year: Arno Eigenwillig provided great assistance in all respects, a special...
A faster deterministic algorithm for minimum cycle basis in directed graphs (2006)
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph...
Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Reliable and efficient computational geometry via controlled perturbation (2006)
Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff
Abstract. Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate inputs. We call such algorithms idealistic. Executing an idealistic algorithm with floating point...
ii Datum des Kolloquiums: 14. 05. 2007 (2006)
Annamária Kovács, Dekan Prof, Dr. Thorsten Herfet, Vorsitzender Prof, Dr. Raimund Seidel, ...
iii Abstract. The thesis deals with problems from two distint areas of scheduling theory. In the first part we consider the preemptive Sum Multicoloring (pSMC) problem. In an instance of pSMC,...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
Abstract. We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum...
nationality Hellenic Education 2003–2006 PhD in Computer Science (2006)
Summa Cum Laude, Advisor Prof, Dr. Kurt Mehlhorn
date of birth 14/04/1979
Irving, Robert W., Kavitha, Telikepalli, Mehlhorn, Kurt, Michail, Dimitrios, Paluch, Katarzyna
Suppose that each member of a set A of applicants ranks a subset of a set P of posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
New bounds for the Descartes method (2006)
Krandick, Werner, Mehlhorn, Kurt
We give a new bound for the number of recursive subdivisions in the Descartes method for polynomial real root isolation. Our proof uses Ostrowski’s theory of normal power series from 1950 which has...
Reply to "Backward Error Analysis ..." (2006)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Gavrilova, Marina, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause implementations...
Reliable and Efficient Computational Geometry Via Controlled Perturbation (2006)
Mehlhorn, Kurt, Osbild, Ralf, Sagraloff, Michael, Bugliesi, Michele, Preneel, Bart, Sassone, Vladimir, ...
Most algorithms of computational geometry are designed for the Real-RAM and non-degenerate input. We call such algorithms idealistic. Executing an idealistic algorithm with floating point arithmetic...
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (2006)
Hariharan, Ramesh, Telikepalli, Kavitha, Mehlhorn, Kurt, Bugliesi, Michele, Preneel, Bart, Sassone, Vladimir, ...
We consider the problem of computing a minimum cycle basis in a directed graph. The input to this problem is a directed graph G whose edges have non-negative weights. A cycle in this graph is...
Reliable and Efficient Geometric Computing (2006)
Mehlhorn, Kurt, Calamoneri, Tiziana, Finocchi, Irene, Italiano, Giuseppe F.
Reliable implementation of geometric algorithms is a notoriously difficult task. Algorithms are usually designed for the Real-RAM, capable of computing with real numbers in the sense of mathematics,...
Implementing Minimum Cycle Basis Algorithms (2006)
Mehlhorn, Kurt, Michail, Dimitrios
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3...
Polyline Fitting of Planar Points under Min-sum Criteria (2006)
Aronov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Matching Algorithms are Fast in Sparse Random Graphs (2006)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum...
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs (2006)
Kratsch, Dieter, McConnell, Ross, Mehlhorn, Kurt, Spinrad, Jeremy P.
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been...
A Descartes Algorithms for Polynomials with Bit-Stream Coefficients (2006)
Mehlhorn, Kurt, Eigenwillig, Arno, Kettner, Lutz, Krandick, Werner, Schmitt, Susanne, Wolpert, Nicola
The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In...
Polyline fitting of planar points under min-sum criteria (2006)
ARONOV, BORIS, ASANO, TETSUO, KATOH, NAOKI, MEHLHORN, KURT, TOKUYAMA, TAKESHI
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs (2005)
Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have non-negative weights assigned to them. We give an Õ(m4 n)...
Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt
controlled perturbation, floating
Exacus: Efficient and exact algorithms for curves and surfaces (2005)
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, ...
Abstract. We present the first release of the EXACUS C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness,...
A Descartes algorithm for polynomials with bit-stream coefficients (2005)
Arno Eigenwillig, Lutz Kettner, Werner Kr, Kurt Mehlhorn, Susanne Schmitt, Nicola Wolpert
Abstract. The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite)...
Exacus: Efficient and exact algorithms for curves and surfaces (2005)
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, ...
Abstract. We present the first release of the EXACUS C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness,...
A Descartes algorithm for polynomials with bit-stream coefficients (2005)
Arno Eigenwillig, Lutz Kettner, Werner Kr, Kurt Mehlhorn, Susanne Schmitt, Nicola Wolpert
Abstract. The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite)...
Implementing Minimum Cycle Basis Algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph G = (V, E) with n vertices and m edges. We describe an e#cient implementation of an O(m algorithm...
Network Problems with Non-Polynomial (2005)
Weights And Applications, Kurt Mehlhorn, Dimitrios Michail
The most e#cient algorithms for several network problems like minimum cost flow and the maximum weight matching problem follow the primal-dual paradigm. These algorithms perform arithmetic (additions...
EXACUS: Efficient and Exact Algorithms for Curves and Surfaces (2005)
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, ...
We present the first release of the EXACUS C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of...
Towards Optimal Multiple Selection (2005)
Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter Sanders, Peter S
The multiple selection problem asks for the elements of rank r1 , r2 , . . . , rk from a linearly ordered set of n elements. Let B denote the information theoretic lower bound on the number of...
A Descartes Algorithm for Polynomials with Bit-Stream Coefficients (2005)
Arno Eigenwillig, Lutz Kettner, Werner Krandick, Kurt Mehlhorn, Susanne Schmitt, Nicola Wolpert
The Descartes method is an algorithm for isolating the real roots of square-free polynomials with real coefficients. We assume that coefficients are given as (potentially infinite) bit-streams. In...
Algorithms to Compute Minimum Cycle Basis in Directed Graphs (2005)
Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have nonnegative weights assigned to them. In this problem a associated with...
Cycle Bases of Graphs and Sampled Manifolds (2005)
Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga
... are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the sample. We show that, under...
New constructions of (α, β)-spanners and purely additive spanners (2005)
Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie
An α�β-spanner of an unweighted graph G is a subgraph H that approximates distances in G in the following sense. For any two vertices u�v: δH u�v�αδG u�v β, where δG is the distance...
Cycle bases of graphs and sampled manifolds (2005)
Craig Gotsman, Kanela Kaligosi, Kurt Mehlhorn, Dimitrios Michail, Evangelia Pyrga
Point samples of a surface in R 3 are the dominant output of a multitude of 3D scanning devices. The usefulness of these devices rests on being able to extract properties of the surface from the...
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Lutz Kettner, Kurt Mehlhorn, ...
Project funded by the European Community under the “Information Society Technologies” Programme (1998–2002)
Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of computing a minimum cycle basis in a directed graph G with m arcs and n vertices. The arcs of G have nonnegative weights assigned to them. In this problem a {−1,0,1}...
Implementing minimum cycle basis algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper, we consider the problem of computing a minimum cycle basis of an undirected graph G = (V,E) with n vertices and m edges. We describe an efficient implementation of an O(m3 + mn2 log n)...
Towards optimal multiple selection (2005)
Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, Peter S
Abstract. The multiple selection problem asks for the elements of rank r1, r2,..., rk from a linearly ordered set of n elements. Let B denote the information theoretic lower bound on the number of...
Implementing minimum cycle basis algorithms (2005)
Kurt Mehlhorn, Dimitrios Michail
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph G = (V, E) with n vertices and m edges. We describe an efficient implementation of an O(m 3 + mn 2 log...
Implementing Minimum Cycle Basis Algorithms (2005)
Mehlhorn, Kurt, Michail, Dimitrios, Nikoletseas, Sotiris
In this paper we consider the problem of computing a minimum cycle basis of an undirected graph $G = (V,E)$ with $n$ vertices and $m$ edges. We describe an efficient implementation of an $O(m^3 +...
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs (2005)
Kavitha, Telikepalli, Mehlhorn, Kurt, Diekert, Volker, Durand, Bruno
Controlled Perturbation for Delaunay Triangulations (2005)
Funke, Stefan, Klein, Christian, Mehlhorn, Kurt, Schmitt, Susanne
Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model of computation and for inputs in general position. Real inputs may be degenerate and floating point...
A Descartes algorithm for polynomials with bit-stream coefficients (2005)
Eigenwillig, Arno, Kettner, Lutz, Krandick, Werner, Mehlhorn, Kurt, Schmitt, Susanne, Wolpert, Nicola, ...
EXACUS: Efficient and exact algorithms for curves and surfaces (2005)
Berberich, Eric, Eigenwillig, Arno, Hemmer, Michael, Hert, Susan, Kettner, Lutz, Mehlhorn, Kurt, ...
We present the first open-source release of the C\texttt{++} libraries of the \textsc{Exacus} project of the Max-Planck-Institut f{\"u}r Informatik. Our software computes arrangements of curves and...
New Constructions of (alpha, beta)-Spanners and Purely Additive Spanners (2005)
Baswana, Surender, Kavitha, Telikepalli, Mehlhorn, Kurt, Pettie, Seth
Pareto-optimality in house allocation problems (2005)
Abraham, David, Mehlhorn, Kurt, Fleischer, Rudolf, Trippen, G.
04301 Abstracts Collection -- Cache-Oblivious and Cache-Aware Algorithms (2005)
Arge, Lars, Bender, Michael A., Demaine, Erik, Leiserson, Charles, Mehlhorn, Kurt
The Dagstuhl Seminar 04301 ``Cache-Oblivious and Cache-Aware Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl, from 18.07.2004 to 23.07.2004. During...
An efficient graph algorithm for dominance constraints (2004)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner,Lutz, Mehlhorn,Kurt, Pion,Sylvain, Schirra,Stefan, Yap,Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn,Kurt, Michail,Dimitrios, Telikepalli,Kavitha, Paluch,Katarzyna
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov,Boris, Asano,Tetsuo, Katoh,Naoki, Mehlhorn,Kurt, Tokuyama,Takeshi
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
An empirical comparison of software for constructing arrangements of curved arcs (2004)
Berberich,Eric, Eigenwillig,Arno, Emiris,Ioannis, Fogel,Efraim, Hemmer,Michael, Halperin,Dan, ...
EXACUS : Efficient and Exact Algorithms for Curves and Surfaces (2004)
Berberich,Eric, Eigenwillig,Arno, Hemmer,Michael, Hert,Susan, Kettner,Lutz, Mehlhorn,Kurt, ...
The LEDA class real number - extended version (2004)
Funke,Stefan, Mehlhorn,Kurt, Schmitt,Susanne, Burnikel,Christoph, Fleischer,Rudolf, Schirra,Stefan
Classroom examples of robustness problems in geometric computations (2004)
Kettner,Lutz, Mehlhorn,Kurt, Pion,Sylvain, Schirra,Stefan, Yap,Chee
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Diekert, Volker, Habib, Michel
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Paluch, Katarzyna, Díaz, Josep, Karhumäki, Juhani, ...
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
An empirical comparison of software for constructing arrangements of curved arcs (2004)
Berberich, Eric, Eigenwillig, Arno, Emiris, Ioannis, Fogel, Efraim, Hemmer, Michael, Halperin, Dan, ...
EXACUS : Efficient and Exact Algorithms for Curves and Surfaces (2004)
Berberich, Eric, Eigenwillig, Arno, Hemmer, Michael, Hert, Susan, Kettner, Lutz, Mehlhorn, Kurt, ...
The LEDA class real number - extended version (2004)
Funke, Stefan, Mehlhorn, Kurt, Schmitt, Susanne, Burnikel, Christoph, Fleischer, Rudolf, Schirra, Stefan
Classroom examples of robustness problems in geometric computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Pareto optimality in house allocation problems (2004)
David J. Abraham, Katarína Cechlárová, David F. Manlove, Kurt Mehlhorn
Abstract. We study Pareto optimal matchings in the context of house allocation problems. We present an O ( √ nm) algorithm, based on Gale’s Top Trading Cycles Method, for finding a maximum...
Rahul Ray, Rahul Ray, Dekan Prof, Gutachter Prof, ...
Dedicated to my parents
Rahul Ray, Rahul Ray, Dekan Prof, Gutachter Prof, ...
Dedicated to my parents
der Naturwissenschaftlich-Technischen Fakultäten (2004)
René Beier, Dekan Prof, Dr. Jörg Eschmeier, Vorsitzender Prof, Dr. Raimund Seidel, Erstgutachter Prof, ...
We investigate the performance of exact algorithms for hard optimization problems under random inputs. In particular, we prove various structural properties that lead to two general average-case...
Point containment in the integer hull of a polyhedron (2004)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is dened by m inequalities, with coecients of at most ' bits can be solved in time O(m + ') in the...
Classroom Examples of Robustness Problems In Geometric Computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in order of preference, possibly...
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
Abstract. We consider the problem of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a nonempty subset of posts in order of preference, possibly...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating-point arithmetic for the assumed real arithmetic may cause implementations...
Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
Suppose that each member of a set�of applicants ranks a subset of a set Èof posts in an order of preference, possibly involving ties. A matching is a set of (applicant, post) pairs such that each...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee Yap, Inria Sophia
Abstract. The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause...
Classroom examples of robustness problems in geometric computations (2004)
Lutz Kettner, Lutz Kettner, Kurt Mehlhorn, Kurt Mehlhorn, Sylvain Pion, Sylvain Pion, ...
Project funded by the European Community
David J. Abraham, Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn
We consider the problem of matching a set of applicants to a set of posts, where each applicant ranks a non-empty subset of posts in an order of preference, possibly involving ties. We say that a...
A faster algorithm for minimum cycle basis of graphs (2004)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail
Abstract. In this paper we consider the problem of computing a minimum cycle basis in a graph G with m edges and n vertices. The edges of G have non-negative weights on them. The previous best result...
Pareto optimality in house allocation problems (2004)
David J. Abraham, Katarína Cechlárová, David F. Manlove, Kurt Mehlhorn
Abstract. We study Pareto optimal matchings in the context of house allocation problems. We present an O ( √ nm) algorithm, based on Gale’s Top Trading Cycles Method, for finding a maximum...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Diekert, Volker, Habib, Michel
A Faster Algorithm for Minimum Cycle Basis of Graphs (2004)
Mehlhorn, Kurt, Michail, Dimitrios, Telikepalli, Kavitha, Paluch, Katarzyna, Díaz, Josep, Karhumäki, Juhani, ...
In this paper we consider the problem of computing a minimum cycle basis in a graph $G$ with $m$ edges and $n$ vertices. The edges of $G$ have non-negative weights on them. The previous best result...
An efficient graph algorithm for dominance constraints (2003)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui,Marcel, Funke,Stefan, Kwappik,Carsten, Mehlhorn,Kurt, Seel,Michael, Schömer,Elmar, ...
Granados,Miguel, Hachenberger,Peter, Hert,Susan, Kettner,Lutz, Mehlhorn,Kurt, Seel,Michael
We describe a data structure for three-dimensional Nef complexes, algorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were introduced by...
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2003)
Althaus,Ernst, Duchier,Denys, Koller,Alexander, Mehlhorn,Kurt, Niehren,Joachim, Thiel,Sven
Smoothed Analysis of Three Combinatorial Problems (2003)
Banderier,Cyril, Beier,Rene, Mehlhorn,Kurt
Smoothed analysis combines elements over worst-case and average case analysis. For an instance $x$, the smoothed complexity is the average complexity of an instance obtained from $x$ by a...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui, Marcel, Funke, Stefan, Kwappik, Carsten, Mehlhorn, Kurt, Seel, Michael, Schömer, Elmar, ...
Granados, Miguel, Hachenberger, Peter, Hert, Susan, Kettner, Lutz, Mehlhorn, Kurt, Seel, Michael, ...
We describe a data structure for three-dimensional Nef complexes, algorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were introduced by...
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2003)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Smoothed Analysis of Three Combinatorial Problems (2003)
Banderier, Cyril, Beier, Rene, Mehlhorn, Kurt, Rovan, Branislav, Vojtáš, Peter
Smoothed analysis combines elements over worst-case and average case analysis. For an instance $x$, the smoothed complexity is the average complexity of an instance obtained from $x$ by a...
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Abstract. Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify...
Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Michael Seel, ...
Project funded by the European Community under the “Information Society Technologies”
Certifying algorithms for recognizing interval graphs and permutation graphs (2003)
Dieter Kratsch, Ross M. Mcconnell, Kurt Mehlhorn, Jeremy P. Spinrad
Abstract. A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has...
When I was asked to contribute to a volume dedicated to Thomas Ottmann’s sixtieth birthday, I
Smoothed analysis of three combinatorial problems (2003)
Cyril Banderier, Kurt Mehlhorn, Rene Beier
Smoothed analysis combines elements over worst-case and average case analysis. For an instance x the smoothed complexity is the average complexity of an instance obtained from x by a perturbation....
Abstract. We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specied and the goal is to...
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify normal...
Boolean Operations on 3D Selective Nef Complexes (2003)
Data Structure Algorithms, Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, ...
this paper has been partially supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG - Effective Computational Geometry for Curves and...
Strongly Stable Matchings in Time O(nm) (2003)
Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna Paluch
An instance of the stable marriage problem is an undirected bipartite graph G = (X [W;E) with linearly ordered adjacency lists; ties are allowed. A matching M is a set of edges no two of which share...
Smoothed Analysis of Three Combinatorial Problems (2003)
Cyril Banderier, Cyril B, Rene Beier, Kurt Mehlhorn
Smoothed analysis combines elements over worst-case and average case analysis. For an instance x, the smoothed complexity is the average complexity of an instance obtained from x by a perturbation....
Certifying Algorithms for Recognizing Interval Graphs and Permutation (2003)
Graphs Dieter Kratsch, Dieter Kratsch, Ross M. Mcconnell, Kurt Mehlhorn, Jeremy P. Spinrad
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been...
An Efficient Graph Algorithm for Dominance Constraints (2003)
Ernst Althaus, Denys Duchier, Alexander Koller, Kurt Mehlhorn, Joachim Niehren, Sven Thiel
Dominance constraints are logical descriptions of trees that are widely used in computational linguistics. Their general satisfiability problem is known to be NPcomplete. Here we identify normal...
When I was asked to contribute to a volume dedicated to Thomas Ottmann’s sixtieth birthday,
Peter Hachenberger, Lutz Kettner, Kurt Mehlhorn
Nef polyhedra in d-dimensional space are the closure of half-spaces under boolean set operations. In consequence, they can represent non-manifold situations, open and closed sets, mixed-dimensional...
Miguel Granados, Peter Hachenberger, Susan Hert, Lutz Kettner, Kurt Mehlhorn, Michael Seel
Abstract. We describe a data structure for three-dimensional Nef complexes, algorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were...
External-Memory Breadth-First Search with Sublinear I/O (2002)
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O(...
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons (2002)
Berberich,Eric, Eigenwillig,Arno, Hemmer,Michael, Hert,Susan, Mehlhorn,Kurt, Schömer,Elmar
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus,Ernst, Bockmayr,Alexander, Elf,Matthias, Kasper,Thomas, Jünger,Michael, Mehlhorn,Kurt
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
All-Pairs Shortest-Paths Computation in the Presence of Negative Cycles (2002)
Mehlhorn,Kurt, Priebe,Volker, Schäfer,Guido, Sivadasan,Naveen
We describe the implementation of an algorithm which solves the weighted matching problem in general graphs with $n$ vertices and $m$ edges in time $O(nm \log n)$. Our algorithm is a variant of the...
Geometric Computing with CGAL and LEDA (2002)
Mehlhorn, Kurt, Schirra, Stefan
LEDA and CGAL are platforms for combinatorial and geometric computing. We discuss the use of LEDA and CGAL for geometric computing and show that they provide a unique framework for exact efficient...
External-Memory Breadth-First Search with Sublinear I/O (2002)
Mehlhorn, Kurt, Meyer, Ulrich, Möhring, Rolf, Raman, Rajeev
Breadth-first search (BFS) is a basic graph exploration technique. We give the first external-memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm requires O(...
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons (2002)
Berberich, Eric, Eigenwillig, Arno, Hemmer, Michael, Hert, Susan, Mehlhorn, Kurt, Schömer, Elmar, ...
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately...
SCIL - Symbolic Constraints in Integer Linear Programming. (2002)
Althaus, Ernst, Bockmayr, Alexander, Elf, Matthias, Kasper, Thomas, Jünger, Michael, Mehlhorn, Kurt, ...
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint...
All-Pairs Shortest-Paths Computation in the Presence of Negative Cycles (2002)
Mehlhorn, Kurt, Priebe, Volker, Schäfer, Guido, Sivadasan, Naveen
Mehlhorn, Kurt, Schäfer, Guido
We describe the implementation of an algorithm which solves the weighted matching problem in general graphs with $n$ vertices and $m$ edges in time $O(nm \log n)$. Our algorithm is a variant of the...
External-memory breadth-first search with sublinear I/O (2002)
Abstract. Breadth-first search (BFS) is a basic graph exploration technique. We give the first external memory algorithm for sparse undirected graphs with sublinear I/O. The best previous algorithm...
SCIL -- Symbolic Constraints in Integer Linear Programming (2002)
Ernst Althaus, Thomas Kasper, Alexander Bockmayr, Michael Jünger, Matthias Elf, Kurt Mehlhorn
We describe SCIL. SCIL introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute...
SCIP – symbolic constraints in integer linear programming (2002)
Ernst Althaus, Thomas Kasper, Alexander Bockmayr, Michael Junger, Kurt Mehlhorn
We describe SCIL. SCIL introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute...
A computational basis for conic arcs and Boolean operations on conic polygons (2002)
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Kurt Mehlhorn, Elmar Schömer
Abstract. We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that...
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons (2002)
Eric Berberich, Arno Eigenwillig, Michael Hemmer, Susan Hert, Kurt Mehlhorn, Elmar Schömer
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately...
All-pairs shortest-paths computation in the presence of negative cycles (2001)
Kurt Mehlhorn, Volker Priebe, Naveen Sivadasan
We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n 2 log n), where the arcs are assigned real, possibly negative...
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
A Separation Bound for Real Algebraic Expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Exact computation with leda real - theory and geometric applications (2001)
The number type leda real provides exact computation for a subset of real algebraic numbers: Every integer is a leda real, and leda reals are closed under the basic arithmetic operations +, −, ∗,...
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Traveling salesman-based curve reconstruction in polynomial time (2001)
Abstract. An instance of the curve reconstruction problem is a finite sample set V of an unknown collection of curves γ. The task is to connect the points in V in the order in which they lie on γ....
An Efficient Algorithm for the Configuration Problem of Dominance Graphs (2001)
Althaus, Ernst, Duchier, Denys, Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim, Thiel, Sven
Dominance constraints are logical tree descriptions originating from automata theory that have multiple applications in computational linguistics. The satisfiability problem of dominance constraints...
Exact computation with leda_real - Theory and geometric applications (2001)
Mehlhorn, Kurt, Schirra, Stefan, Alefeld, Götz, Rohn, Jiri, Rump, Siegfried M., Yamamoto, Tetsuro
Traveling Salesman-Based Curve Reconstruction in Polynomial Time (2001)
Althaus, Ernst, Mehlhorn, Kurt
An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$....
CNOP - {A} Package for Constrained Network Optimization (2001)
Mehlhorn, Kurt, Ziegelmann, Mark, Buchsbaum, Adam L., Snoeyink, Jack
We present a generic package for resource constrained network optimization problems. We illustrate the flexibility and the use of our package by solving four applications: route planning, curve...
A Separation Bound for Real Algebraic Expressions (2001)
Burnikel, Christoph, Funke, Stefan, Mehlhorn, Kurt, Schirra, Stefan, Schmitt, Susanne
Mehlhorn, Kurt, Schäfer, Guido
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
Scanning multiple sequences via cache memory (2000)
We consider the simple problem of scanning multiple sequences. There are k sequences of total length N which are to be scanned concurrently. One pointer into each sequence is maintained and an...
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint (2000)
Abstract. We present narrowing algorithms for the sortedness and the alldierent constraint which achieve bound-consistency. The algorithm for the sortedness constraint takes as input 2n intervals X1;...
Abstract. We describe the implementation of an O(nm log n) algorithm for weighted matchings in general graphs. The algorithm is a variant of the algorithm of Galil, Micali, and Gabow [GMG86] and...
TSP-Based Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Schirra
An instance of the curve reconstruction problem is a nite sample V of an unknown curve . The task is to connect the points in V in the order in which they lie on . Several new algorithms for the...
Experiments on Curve Reconstruction (2000)
Ernst Althaus, Kurt Mehlhorn, Stefan Näher, Stefan Schirra
An instance of the curve reconstruction problem is a finite sample V of an unknown curve gamma...
TSP-Based Curve Reconstruction in Polynomial Time (2000)
An instance of the curve reconstruction problem is a nite sample V of an unknown curve and the task is to connect the points in V in the order in which they lie on . Giesen [Gie99] showed recently...
A Polynomial-Time Fragment of Dominance Constraints (2000)
Alexander Koller, Kurt Mehlhorn, Joachim Niehren
Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satis ability problem is known to be NP-complete. Here we identify...
LOOK - A Lazy Object-Oriented Kernel for Geometric Computation (2000)
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the...
Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model (2000)
Colin Cooper Alan, Kurt Mehlhorn, Volker Priebe
We study the average-case complexity of shortest-paths problems in the vertex-potential model. The vertex-potential model is a family of probability distributions on complete directed graphs with...
An Empirical Comparison of Software for Constructing Arrangements of Curved Arcs (2000)
Sylvain Pion, Monique Teillaud, Efraim Fogel, Dan Halperin, Ron Wein, Ioannis Emiris, ...
Arrangements of planar curves are fundamental structures in computational geometry.
Constraint Programming and Graph Algorithms (2000)
mming paradigm, that allows one to formulate computational problems at a very high level. A computational problem is formulated as a constraint. A constraint is simply a conjunction of formulae of...
Technique For Making, Kurt Mehlhorn, Michael Seel
Many geometric algorithms that are usually formulated for points and segments generalize easily to inputs also containing rays and lines. The sweep algorithm for segment intersection is a...
Resource Constrained Shortest Paths (2000)
Kurt Mehlhorn And, Kurt Mehlhorn
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and...
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint (2000)
Abstract. We present narrowing algorithms for the sortedness and the alldifferent constraint which achieve bound-consistency. The algorithm for the sortedness constraint takes as input 2n intervals...
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the...
Infimaximal frames: A technique for making lines look like segments (2000)
Many geometric algorithms that are usually formulated for points and segments generalize easily to inputs also containing rays and lines. The sweep algorithm for segment intersection is a...
Many geometric algorithms that are usually formulated for points and segments generalize easily to inputs also containing rays and lines. The sweep algorithm for segment intersection is a...
Resource constrained shortest paths (2000)
Abstract. The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and...
Average-Case Complexity of Shortest-Paths Problems in the Vertex-Potential Model (2000)
Cooper, Colin, Frieze, Alan M., Mehlhorn, Kurt, Priebe, Volker
We study the average-case complexity of shortest-paths problems in the vertex-potential model. The vertex-potential model is a family of probability distributions on complete directed graphs with...
TSP-Based Curve Reconstruction in Polynomial Time (2000)
Althaus, Ernst, Mehlhorn, Kurt
An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$....
A strong and easily computable separation bound for arithmetic expressions involving radicals (2000)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We consider arithmetic expressions over operators + , - , * , / , and $\sqrt[k]$ , with integer operands. For an expression E having value $\xi$ , a separation bound sep (E) is a positive real number...
Geometric Computing with CGAL and LEDA (2000)
Mehlhorn, Kurt, Schirra, Stefan, Laurent, Pierre-Jean, Sablonnière, Paul, Schumaker, Larry L.
A polyhedral approach to sequence alignment problems (2000)
Kececioglu, John, Lenhof, Hans-Peter, Mehlhorn, Kurt, Mutzel, Petra, Reinert, Knut, Vingron, Martin
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint (2000)
Mehlhorn, Kurt, Thiel, Sven, Dechter, Rina
We present narrowing algorithms for the sortedness and the alldifferent constraint which achieve bound-consistency. The algorithm for the sortedness constraint takes as input $2n$ intervals $X_1,...
Resource Constrained Shortest Paths (2000)
Mehlhorn, Kurt, Ziegelmann, Mark, Paterson, Mike
The resource constrained shortest path problem (CSP) asks for the computation of a least cost path obeying a set of resource constraints. The problem is NP-complete. We give theoretical and...
Experiments on curve reconstruction (2000)
Althaus, Ernst, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan
A Polynomial-Time Fragment of Dominance Constraints (2000)
Koller, Alexander, Mehlhorn, Kurt, Niehren, Joachim
Dominance constraints are a logical language for describing trees that is widely used in computational linguistics. Their general satisfiability problem is known to be NP-complete. Here we identify...
Constraint Programming and Graph Algorithms (2000)
Mehlhorn, Kurt, Montanari, Ugo, Rolim, José D. P., Welzl, Emo
Implementation of $O(nm \log n)$ weighted matchings: The power of data structures (2000)
Mehlhorn, Kurt, Schäfer, Guido, Näher, Stefan, Wagner, Dorothea
We describe the implementation of an $O(nm \log n)$ algorithm for weighted matchings in general graphs. The algorithm is a variant of the algorithm of Galil, Micali, and Gabow and requires the use of...
Curve reconstruction: Connecting dots with good reason (2000)
Dey, Tamal K., Mehlhorn, Kurt, Ramos, Edgar A.
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed...
LEDA: A Platform for Combinatorial and Geometric Computing (1999)
Kurt Mehlhorn, Christian Uhrig
Abstract. We give an overview of the LEDA platform for combinatorial and geometric computing and an account of its development. We discuss our motivation for building LEDA and to what extent we have...
An analysis of the highest-level selection rule in the preflow-push max-flow algorithm (1999)
Joseph Cheriyan, Kurt Mehlhorn
Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level...
Structural filtering: A paradigm for efficient and exact geometric programs (1999)
Stefan Funke, Kurt Mehlhorn, Stefan Näher
We introduce a new filtering technique that can be used in the implementation of geometric algorithms called "structural filtering". Using this filtering techniques we gain about 20 % when...
Structural Filtering - A Paradigm for Efficient and Exact Geometric Programs (1999)
Stefan Funke, Kurt Mehlhorn, Stefan Näher
We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called "structural filtering". Using this filtering technique we gain about...
Curve Reconstruction: Connecting Dots with Good Reason (1999)
Tamal K. Dey, Kurt Mehlhorn, Edgar A. Ramos
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a suciently dense sample of a closed smooth...
Curve Reconstruction: Connecting Dots with Good Reason (1999)
Tamal K. Dey, Kurt Mehlhorn, Edgar A. Ramos
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a suÆciently dense sample of a closed smooth...
LEDA-SM - A Platform for Secondary Memory Computation (1999)
Andreas Crauser, Kurt Mehlhorn
Contents 1 Introduction 3 1.1 License Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . ....
On the expected depth of random circuits (1999)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
Abstract: In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from...
An analysis of the highest-level selection rule in the preflow-push max-flow algorithm (1999)
Cheriyan, Joseph, Mehlhorn, Kurt
Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level...
Checking geometric programs or verification of geometric structures (1999)
Mehlhorn, Kurt, Näher, Stefan, Seel, Michael, Seidel, Raimund, Schilz, Thomas, Schirra, Stefan, ...
LEDA-SM : Extending LEDA to Secondary Memory (1999)
Crauser, Andreas, Mehlhorn, Kurt, Vitter, Jeffrey S., Zaroliagis, Christos D.
During the last years, many software libraries for \emph{in-core} computation have been developed. Most internal memory algorithms perform very badly when used in an \emph{external memory} setting....
Efficient exact geometric computation made easy (1999)
Burnikel, Christoph, Fleischer, Rudolf, Mehlhorn, Kurt, Schirra, Stefan
We show that the combination of the CGAL framework for geometric computation and the number type leda-real yields easy-to-write, correct and efficient geometric programs.
A correctness certificate for the Stoer-Wagner min-cut algorithm (1999)
Arikati, Srinivasa Rao, Mehlhorn, Kurt
The Stoer–Wagner algorithm computes a minimum cut in a weighted undirected graph. The algorithm works in n−1 phases, where n is the number of nodes of G. Each phase takes time O(m+nlogn), where m...
Curve reconstruction: Connecting dots with good reason (1999)
Dey, Tamal K., Mehlhorn, Kurt, Ramos, Edgar A.
Curve reconstruction algorithms are supposed to reconstruct curves from point samples. Recent papers present algorithms that come with a guarantee: Given a sufficiently dense sample of a closed...
I/O-optimal computation of segment intersections (1999)
Crauser, Andreas, Ferragina, Paolo, Mehlhorn, Kurt, Meyer, Ulrich, Ramos, Edgar A., Abello, James M., ...
LEDA: a platform for combinatorial and geometric computing (1999)
Contents Preface page xi 1 Introduction 1 1.1 Some Programs 1 1.2 The LEDA System 8 1.3 The LEDA Web-Site 10 1.4 Systems that Go Well with LEDA 11 1.5 Design Goals and Approach 11 1.6 History 13 2...
On the Expected Depth of Random Circuits (1999)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyse the expected depth of random circuits of fixed fanin f . Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Ten Years of LEDA Some Thoughts (Abstract) (1999)
Mehlhorn, Kurt, Vitter, Jeffrey S., Zaroliagis, Christos D.
Stefan Näher and I started the work on LEDA [LED] in the spring on 1989. Many collegues and students have contributed to the project since then. A first publication appeared in the fall of the same...
The Engineering of Some Bipartite Matching Programs (1999)
Mehlhorn, Kurt, Rangan, C. Pandu, Raman, Venkatesh, Ramanujam, R.
Faster Algorithms for the Shortest Path Problem, (1998)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
This document investigates efficient implementations of Dijkstra's shortest path algorithm. The authors propose a new data structure, called the redistributive heap, for use in this algorithm. On a...
On the expected depth of random circuits (1998)
Arya, Sunil, Golin, Mordecai J., Mehlhorn, Kurt
In this paper we analyze the expected depth of random circuits of fixed fanin f. Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Polyline fitting of planar points under min-sum criteria (1998)
Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
2nd Workshop on Algorithm Engineering WAE'98 - Proceedings (1998)
Kurt Mehlhorn (ed.), Kurt Mehlhorn, Kurt Mehlhorn
We consider a problem of reconstructing a discrete structure from unstructured numerical data. The problem arises in the computer-aided design of machines, motor vehicles, and other technical...
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm (1998)
Joseph Cheriyan, Kurt Mehlhorn
Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level...
From Algorithms to Working Programs On the Use of Program Checking in LEDA (1998)
. We report on the use of program checking in the LEDA library of efficient data types and algorithms. 1 Introduction LEDA [MN95,MNU97,MN98] is a collection of implementations of data structures and...
A Polyhedral Approach to Sequence Alignment Problems (1998)
John D. Kececioglu, Hans-peter Lenhof, Kurt Mehlhorn, Petra Mutzel, Knut Reinert, Martin Vingron
We study two new problems in sequence alignment both from a practical and a theoretical view, using tools from combinatorial optimization to develop branchand -cut algorithms. The Generalized Maximum...
Komplexitätstheorie: WS 98/99 (1998)
Kurt Mehlhorn, Laurant Porkolap
ent checkers. There could be a reason for that, namely that the problems have no checkers. Complexity theory could give the answer and so I hope that I learn something for my problem in the course. 4...
Convex Hulls in Higher-dimensional Space (1998)
Michael Müller, Joachim Ziegler, Kurt Mehlhorn, Michael Seel
We define and implement the data type chull . It maintains convex hulls in arbitrary dimensions and supports insertions of points and membership queries. The interior of the hull and the boundary of...
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm (1998)
Joseph Cheriyan, Kurt Mehlhorn
Consider the problem of finding a maximum flow in a network. Goldberg and Tarjan introduced the preflow-push method for solving this problem. When this method is implemented with the highest-level...
On the Expected Depth of Random Circuits (1998)
Sunil Arya, Mordecai J. Golin, Kurt Mehlhorn
: In this paper we analyze the expected depth of random circuits of fixed fanin f: Such circuits are built a gate at a time, with the f inputs of each new gate being chosen randomly from among the...
Delaunay Triangulations in Higher-dimensional Space (1998)
We define and implement the data type delaunay . It maintains Delaunay triangulations in arbitrary dimensions and supports insertions of points, lookup and location queries. The delaunay...
Polyline Fitting of Planar Points under Min-Sum (1998)
Criteria Boris Aronov, Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama Polytechnic
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Polyline Fitting of Planar Points under Min-Sum Criteria (1998)
Boris Aronov Tetsuo, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
Fitting acurv e of a certain type to agiv en set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Certifying Algorithms (A Paper under Construction) (1998)
Kurt Mehlhorn, Arno Eigenwillig, Kanela Kanegossi, Dieter Kratsch, Ross Mcconnel, Uli Meyer, ...
A computational basis for higher-dimensional computational geometry and applications (1998)
Mehlhorn, Kurt, Müller, Michael, Näher, Stefan, Schirra, Stefan, Seel, Michael, Uhrig, Christian, ...
Maximum Network Flow with Floating Point Arithmetic (1998)
Althaus, Ernst, Mehlhorn, Kurt
We discuss the implementation of network flow algorithms in floating point arithmetic. We give an example to illustrate the difficulties that may arise when floating point arithmetic is used without...
A Parallelization of Dijkstra's Shortest Path Algorithm (1998)
Crauser, Andreas, Mehlhorn, Kurt, Meyer, Ulrich, Sanders, Peter, Brim, Lubos, Gruska, Jozef, ...
The single source shortest path (SSSP) problem lacks parallel solutions which are fast and simultaneously work-efficient. We propose simple criteria which divide Dijkstra's sequential SSSP algorithm...
Randomized External-Memory Algorithms for some Geometric Problems (1998)
Crauser, Andreas, Ferragina, Paolo, Mehlhorn, Kurt, Meyer, Ulrich, Ramos, Edgar A.
From Algorithms to Working Programs: On the Use of Program Checking in LEDA (1998)
Mehlhorn, Kurt, Näher, Stefan, Brim, Lubos, Gruska, Jozef, Zlatuska, Jirí
Average-case complexity of shortest-paths problems in the vertex-potential model (1997)
Colin Cooper, Alan Frieze, Kurt Mehlhorn, Volker Priebe
the vertex-potential model*
A Complete Roundness Classification Procedure (1997)
Kurt Mehlhorn, Thomas C. Shermer, Chee K. Yap
We describe a roundness classification procedure, that is, a procedure to determine if the roundness of a planar object I is within some ffl 0 from an ideal circle. The procedure consists of a...
Ulrike Bartuschka, Kurt Mehlhorn, Stefan Näher
We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm [1] based on the LEDA platform of combinatorial and geometric computing [9, 8]. The program computes the...
Average-case complexity of shortest-paths problems in the vertex-potential model (1997)
Colin Cooper, Alan Frieze, Kurt Mehlhorn, Volker Priebe
ABSTRACT: We study the average-case complexity of shortest-paths problems in the vertexpotential model. The vertex-potential model is a family of probability distributions on complete directed graphs...
Kürzeste-Wege-Berechnung bei sehr großen Datenmengen (1997)
Crauser, Andreas, Mehlhorn, Kurt, Meyer, Ulrich, Spaniol, Otto
In diesem Report untersuchen wir die Ein/Ausgabe-Komplexität (I/O Komplexität) des Kürzesten-Wege-Problems mit einem Startknoten (single source shortest path) auf Graphen mit nicht-negativen...
On the All-Pairs Shortest-Path Algorithm of Moffat and {Takaoka} (1997)
Mehlhorn, Kurt, Priebe, Volker
We review how to solve the all-pairs shortest-path problem in a non-negatively weighted digraph with $n$ vertices in expected time $O(n^2 \log n)$. This bound is shown to hold with high probability...
A Branch-And-Cut algorithm for multiple sequence alignment (1997)
Reinert, Knut, Lenhof, Hans-Peter, Mehlhorn, Kurt, Mutzel, Petra, Kececioglu, John
Average-case complexity of shortest-paths problems in the vertex-potential model (1997)
Cooper, Colin, Frieze, Alan M., Mehlhorn, Kurt, Priebe, Volker, Rolim, José
We study the average-case complexity of shortest-paths problems in the vertex-potential model. The vertex-potential model is a family of probability distributions on complete directed graphs with...
A Computational Basis for Higher-dimensional Computational Geometry and Applications (1997)
Mehlhorn, Kurt, Müller, Michael, Näher, Stefan, Schirra, Stefan, Seel, Michael, Uhrig, Christian, ...
The LEDA platform for combinatorial and geometric computing (1997)
Mehlhorn, Kurt, Näher, Stefan, Uhrig, Christian, Degano, Pierpaolo, Gorrieri, Roberto, Marchetti-Spaccamela, Alberto
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
Checking geometric programs or verification of geometric structures (1996)
Kurt Mehlhorn, Stefan Naher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, ...
A program checker verifies that a particular program execution is correct. We give simple and efficient program checkers for some basic geometric tasks. We report about our experiences with program...
Michael Müller, Joachim Ziegler, Kurt Mehlhorn
We define and implement the data type chull. It maintains convex hulls in arbitrary dimensions and supports insertions of points and membership queries. The interior of the hull and the boundary of...
Higher-dimensional Convex Hulls and Delaunay Triangulations Specification and Implementation (1996)
Kurt Mehlhorn, Michael Müller, Stefan Näher, Joachim Ziegler
Introduction We discuss the specification and implementation of the data types convex hull and Delaunay triangulation for higher-dimensional space. We aimed for ffl rich functionality and ease of use...
The LEDA class real number (1996)
Christoph Burnikel, Kurt Mehlhorn, Stefan Schirra
We describe the implementation of the LEDA [MN95, Nah95] data type real. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and...
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1996)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
Checking Geometric Programs or Verification of Geometric Structures (1996)
Mehlhorn, Kurt, Näher, Stefan, Schilz, Thomas, Schirra, Stefan, Seel, Michael, Seidel, Raimund, ...
Komplexitätstheorie und Algorithmik (1996)
Mehlhorn, Kurt, Claus, Volker, Thomas, Wolfgang, Wilhelm, Reinhard
The LEDA Platform for Combinatorial and Geometric Computing (1996)
Mehlhorn, Kurt, Näher, Stefan, Uhrig, Christian, Mayr, Heinrich C.
LEDA - A Platform for Combinatorial and Geometric Computing (1995)
Kurt Mehlhorn, Stefan Näher, Stefan N Aher
Contents Preface page xi 1 Introduction 1 1.1 Some Programs 1 1.2 The LEDA System 8 1.3 The LEDA Web-Site 10 1.4 Systems that Go Well with LEDA 11 1.5 Design Goals and Approach 11 1.6 History 13 2...
On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm (1995)
We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be...
LEDA A Platform for Combinatorial and Geometric Computing (1995)
LEDA is a library of efficient data types and algorithms in combinatorial and geometric computing. The main features of the library are its wide collection of data types and algorithms, the precise...
LEDA - A Platform for Combinatorial and Geometric Computing (1995)
LEDA is a library of efficient data types and algorithms in combinatorial and geometric computing. The main features of the library are its wide collection of data types and algorithms, the precise...
On the All-Pairs Shortest-Path Algorithm (1995)
Of Moffat, Kurt Mehlhorn, Volker Priebe
ABSTRACT: We review how to solve the all-pairs shortest-path problem in a nonnegatively Ž 2 weighted digraph with n vertices in expected time On log n.. This bound is shown to hold with high...
Exact Geometric Computation in LEDA (1995)
Burnikel, Christoph, Könemann, Jochen, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, Uhrig, Christian
A communication-randomness tradeoff for two-processor systems (1995)
Fleischer, Rudolf, Jung, Hermann, Mehlhorn, Kurt
We present a tight tradeoff between the expected communication complexity $\bar{C}$ (for a two-processor system) and the number $R$ of random bits used by any Las Vegas protocol for the...
Lower bounds for set intersection queries (1995)
Dietz, Paul, Mehlhorn, Kurt, Raman, Rajeev, Uhrig, Christian
Experiences with the implementation of geometric algorithms (1995)
Mehlhorn, Kurt, Akl, Selim G., Dehne, Frank, Sack, Jörg-Rüdiger, Santoro, Nicola
LEDA : A Platform for Combinatorial and Geometric Computing (1995)
LEDA is a library of efficient data types and algorithms in combinatorial and geometric computing. The main features of the library are its wide collection of data types and algorithms, the precise...
Implementation of a sweep line algorithm for the straight line segment intersection problem (1994)
We describe a robust and efficient implementation of the Bentley-Ottmann sweep line algorithm [7] based on the LEDA library of efficient data types and algorithms [7]. The program computes the planar...
How to Compute the Voronoi Diagram of Line Segments: Theoretical and Experimental Results (1994)
Burnikel, Christoph, Mehlhorn, Kurt, Schirra, Stefan, Van Leeuwen, Jan
Dynamic Perfect Hashing: Upper and Lower Bounds (1994)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Rohnert, Hans, Tarjan, Robert E.
A lower bound for area-universal graphs (1994)
Bilardi, Gianfranco, Chaudhuri, Shiva, Dubhashi, Devdatt, Mehlhorn, Kurt
We establish a lower bound on the efficiency of rea--universal circuits. The area A u of every graph H that can host any graph G of area (at most) A with dilation d, and congestion c p A= log log A...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
A Complete and efficient algorithm for the intersection of a general ans a convex polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Katrin Dobrindt, Katrin Dobrindt, Kurt Mehlhorn, Kurt Mehlhorn, Mariette Yvinec, Mariette Yvinec, ...
: A polyhedron is any set that can be obtained from the open halfspaces by a finite number of set complement and set intersection operations. We give an efficient and complete algorithm for...
An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm (1993)
Kurt Mehlhorn, Petra Mutzel, Stefan Näher
We describe an implementation of the Hopcroft and Tarjan planarity test and embedding algorithm. The program tests the planarity of the input graph and either constructs a combinatorial embedding (if...
An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm (1993)
Kurt Mehlhorn, Petra Mutzel, Stefan Näher
We describe an implementation of the Hopcroft and Tarjan planarity test and embedding algorithm. The program tests the planarity of the input graph and either constructs a combinatorial embedding (if...
Exact Algorithms for a Geometric Packing Problem (Extended Abstract) (1993)
Kucera, Ludek, Mehlhorn, Kurt, Preis, B., Schwarzenecker, E.
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette, Sack, Jörg-Rüdiger, Santoro, Nicola, ...
Maintaining Discrete Probability Distributions Optimally (1993)
Hagerup, Torben, Mehlhorn, Kurt, Munro, I., Lingas, Andrzej, Karlsson, Rolf, Carlsson, Svante
Lower Bounds for Set Intersection queries (1993)
Dietz, Paul, Mehlhorn, Kurt, Raman, Rajeev, Uhrig, Christian
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette
Un polyedre est tout ensemble qui peut etre obtenu a partir de demi-espaces par un nombre fini d{'}operations de complement et d{'}intersection. Nous proposons ici un algorithme complet et efficace...
Algorithm design and software libraries: Recent developments in the LEDA project (1992)
LEDA (Library of Efficient Data Types and Algorithms) is an ongoing project which aims to build a library of the efficient data structures and algorithms used in combinatorial computing [12]. We...
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...
Simultaneous Inner and Outer Approximation of Shapes (1992)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
Selected Topics from Computational Geometry, Data Structures and Motion Planning (1992)
Fleischer, Rudolf, Fries, Otfried, Mehlhorn, Kurt, Meiser, Stefan, Näher, Stefan, Rohnert, Hans, ...
Four Results on Randomized Incremental Constructions (1992)
Clarkson, Kenneth L., Mehlhorn, Kurt, Seidel, Raimund, Finkel, Alain, Jantzen, Matthias
Tail Estimates for the Space Complexity of Randomised Incremental Algorithms (1992)
Mehlhorn, Kurt, Sharir, Micha, Welzl, Emo, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
Dynamic Point Location in General Subdivisions (1992)
Baumgarten, Hanna, Jung, Hermann, Mehlhorn, Kurt, Frederickson, Grag, Graham, Ron, Hochbaum, Dorit S., ...
Randomized incremental construction of abstract Voronoi diagrams (1992)
Klein, Rolf, Mehlhorn, Kurt, Meiser, Stefan, Buchmann, J., Ganzinger, Harald, Paul, Wolfgang J.
A Time-Randomness Tradeoff for Communication Complexity (1991)
Fleischer, Rudolf, Jung, Hermann, Mehlhorn, Kurt, Van Leeuwen, Jan, Santoro, Nicola
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities (1991)
Alt, Helmut, Guibas, L., Mehlhorn, Kurt, Karp, Richard M., Wigderson, A.
We study strategies for converting randomized algorithms of the Las Vegas type into randomized algorithms with small tail probabilities.
Dynamic Perfect Hashing: Upper and Lower Bounds (1991)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Rohnert, Hans, Tarjan, Robert E.
The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a...
Bounded ordered dictionaries in O(log log N) time and O(n) space (1990)
Abstract. In this paper we show how to implement bounded ordered dictionaries, also called bounded priority queues, in O(log log N) time per operation and O(n) space. Here n denotes the number of...
Can a Maximum Flow be Computed in o(nm) Time (1990)
Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn
Abstract. We show that a maximum flow in a network with n vertices can be computed deterministically in O(n3/logn) time on a uniform-cost RAM. For dense graphs, this improves the previous best bound...
Faster Algorithms for the Shortest Path Problem (1990)
Ravindra K. Ahuja, Kurt Mehlhorn, James B. Orlin, Robert E. Tarjan
Abstract. Efficient implementations of Dijkstra’s shortest path algorithm are investigated. A new data structure, called the radix heap, is proposed for use in this algorithm. On a network with n...
On the Construction of Abstract Voronoi Diagrams (1990)
Mehlhorn, Kurt, Meiser, Stefan, Ó'Dúnlaing, Colm, Choffrut, Christian, Lengauer, Thomas
Can A Maximum Flow be Computed in o(nm) Time? (1990)
Cheriyan, Joseph, Hagerup, Torben, Mehlhorn, Kurt, Paterson, Michael S.
On Simultaneous Inner and Outer Approximation of Shapes (1990)
Fleischer, Rudolf, Mehlhorn, Kurt, Rote, Günter, Welzl, Emo, Yap, Chee-Keng
Alt, Helmut, Fleischer, Rudolf, Kaufmann, Michael, Mehlhorn, Kurt, Näher, Stefan, Schirra, Stefan, ...
Faster algorithms for the shortest path problem (1990)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
On the Construction of Abstract Voronoi Diagrams, II (1990)
Klein, R., Mehlhorn, Kurt, Meiser, Stefan, Asano, Tetsuo, Ibaraki, Toshihide, Imai, Hiroshi, ...
A faster compaction algorithm with automatic jog insertion (1990)
The work of F.M. Maley (Proc. Chapel Hill Conf. on VLSI, p.261-83, 1985) on one-dimensional compaction with automatic jog insertion is refined. More precisely, an algorithm with running time...
Compaction on the torus (1990)
A compacter takes as input a VLSI layout and produces as output an equivalent layout of smaller area. An effective compaction system frees the designer from the details of the design rules, and...
Routing problems in grid graphs (1990)
Kaufmann, Morgan, Mehlhorn, Kurt, Korte, Bernhard, Lovász, László, Prömel, Hans Jürgen, Schrijver, Alexander
a Library of Efficient Data Types and Algorithms (1989)
LEDA is a library of efficient data types and algorithms. At present, its strength is graph algorithms and the data structures related to them. The computational geometry part is evolving. The main...
LEDA: A library of efficient data types and algorithms (1989)
Mehlhorn, Kurt, Näher, Stefan, Kreczmar, Antoni, Mirkowska, Grazyna
Two Versus One Index Register and Modifiable Versus Non-modifiable Programs (1989)
Mehlhorn, Kurt, Paul, Wolfgang J., Ausiello, Giorgio, Dezani-Ciancaglini, Mariangiola, Ronchi Della Rocca, Simonetta
A library of efficient data types and algorithms (1989)
Mehlhorn, Kurt, Näher, S, Kreczmar, Antoni, Mirkowska, Grazyna
Upper and Lower Bounds for the Dictionary Problem (1988)
Dietzfelbinger, Martin, Mehlhorn, Kurt, Rohnert, H., Karlsson, Rolf, Lingas, Andrzej
Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves (1988)
Mehlhorn, Kurt, Yap, Chee-Keng, Lepistö, Timo, Salomaa, Arto
Dynamic Perfect Hashing: Upper and Lower Bounds (1988)
Dietzfelbinger, Martin, Karlin, Anna, Mehlhorn, Kurt, Rohnert, Hans, Tarjan, Robert E.
On Continuous Homotopic One Layer Routing (Extended Abstract) (1988)
Gao, Shaodi, Kaufmann, Michael, Mehlhorn, Kurt, Rülling, Wolfgang, Storb, Christoph, Jerrum, Mark, ...
On Continuous Homotopic One Layer Routing (1988)
Gao, Shaodi, Jerrum, Mark, Kaufmann, Michael, Mehlhorn, Kurt, Rülling, Wolfgang
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Faster Algorithms for the Shortest Path Problem (1988)
Ahuja, Ravindra K., Mehlhorn, Kurt, Orlin, James B., Tarjan, Robert E.
Area-Time Optimal Division for $T=\Omega((\log n)^1+\epsilon)$ (1987)
Mehlhorn, Kurt, Preparata, Franco P.
Area-time optimal VLSI division circuits are described for all computation times in the range for arbitrary > 0.
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
The authors describe a nonuniform deterministic simulation of PRAMs on module parallel computers (MPCs) and on processor networks of bounded degree. The simulating machines have the same number $n$...
On Local Routing of Two-Terminal Nets (1987)
Kaufmann, Michael, Mehlhorn, Kurt, Brandenburg, Franz J., Vidal-Naquet, Guy, Wirsing, Martin
Deterministic Simulation of Idealized Parallel Computers on more Realistic Ones (1987)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Albrecht, Andreas, Jung, Hermann, ...
Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees (1986)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones (1986)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P., Gruska, Jozef, Rovan, Branislav, ...
Routing through a Rectangle (1986)
Mehlhorn, Kurt, Preparata, F. P.
In this paper an O(N log N) algorithm for routing through a rectangle is presented. Consider an n-by-m rectangular grid and a set of N two-terminal nets. A net is a pair of points on the boundary of...
Area-time Optimal Division for T=Omega(log n)$^1+epsilon$" (1986)
Mehlhorn, Kurt, Preparata, Franco P., Monien, Burkhard, Vidal-Naquet, Guy
AT$^2$-Optimal Galois Field Multiplier for {VLSI} (1986)
Fürer, Martin, Mehlhorn, Kurt, Makedon, Fillia, Mehlhorn, Kurt, Papatheodorou, Theodore S., Spirakis, Paul G.
VLSI Algorithms and Architectures, Aegean Workshop on Computing - >> Dublette (1986)
Fürer, Martin, Mehlhorn, Kurt, Makedon, Fillia, Mehlhorn, Kurt, Papatheodorou, Theodore S., Spirakis, Paul G.
VLSI Algorithms and Architectures, Aegean Workshop on Computing - >> Dublette (1986)
Fürer, Martin, Mehlhorn, Kurt, Makedon, Fillia, Mehlhorn, Kurt, Papatheodorou, Theodore S., Spirakis, Paul G.
Sorting Jordan sequences in linear time (1985)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
Deterministic simulation of idealized parallel computers on more realistic ones (1985)
Alt, Helmut, Hagerup, Torben, Mehlhorn, Kurt, Preparata, Franco P.
Space Sweep Solves Intersection of Convex Polyhedra (1984)
Hertel, Stefan, Mäntylä, Martti, Mehlhorn, Kurt, Nievergelt, Jurg
Summary Plane-sweep algorithms form a fairly general approach to two-dimensional problems of computational geometry. No corresponding general space-sweep algorithms for geometric problems in 3-...
Data structures and algorithms. Volume 1 : Sorting and searching (1984)
Mehlhorn, Kurt, Brauer, Wilfried, Rozenberg, Grzegorz, Salomaa, Arto
Data structures and algorithms. Volume 2 : Graph algorithms and NP-completeness (1984)
Mehlhorn, Kurt, Brauer, Wilfried, Rozenberg, Grzegorz, Salomaa, Arto
Sorting Jordan sequences in linear time (1984)
Hoffmann, Kurt, Mehlhorn, Kurt, Rosenstiehl, Pierre, Tarjan, Robert E.
The present paper provides a comprehensive study of the following problem. Consider algorithms which are designed for shared memory models of parallel computation (PRAMs) in which processors are...
The Recognition of Deterministic CFL's in Small Time and Space (1983)
Von Braunmühl, Burchard, Cook, Stephen, Mehlhorn, Kurt, Verbeek, Rutger
Let S(n) be a nice space bound such that log2 n S(n) n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O(n2/S(n)) and space O(S(n)), and this time bound is...
Cost Trade-offs in Graph Embeddings, with Applications (1983)
Hong, Jia-Wei, Mehlhorn, Kurt, Rosenberg, Arnold L.
An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H. There are two natural measures of the cost of a graph embedding, namely, the...
The Theory of Fringe Analysis and Its Application to 2-3 Trees and B-Trees (1982)
Eisenbarth, Bernhard, Ziviani, Nivio, Gonnet, Gaston H., Mehlhorn, Kurt, Wood, Derick
A Probabilistic Algorithm for Vertex Connectivity of Graphs (1982)
Becker, Michael, Degenhardt, W., Doenhardt, J., Hertel, S., Kaninke, G., Kerber, W., ...
Lower bounds on the efficiency of transforming static data structures into dynamic structures (1981)
Cost Tradeoffs in Graph Embeddings, with Applications (Preliminary Version) (1981)
Hong, Jia-Wei, Mehlhorn, Kurt, Rosenberg, Arnold L., Even, Shimon, Kariv, Oded
Partial Match Retrieval in Implicit Data Structures (1981)
Alt, Helmut, Mehlhorn, Kurt, Munro, J. Ian, Gruska, Jozef, Chytil, Michal
Codes: Unequal Probabilities, Unequal Letter Cost (1980)
Altenkamp, Doris, Mehlhorn, Kurt
The construction of alphabetic prefix codes with unequal letter costs and unequal probabilities is considered. A variant of the noiseless coding theorem is proved giving closely matching lower and...
Lower bounds on the efficiency of transforming static data structures into dynamic structures (1980)
We consider search trees under time-varying access probabilities. Let $S = \{ B_1 , \cdots ,B_n \} $ and let $p_i^t $ be the number of accesses to object $B_i $ up to time $t$, $W^t = \sum {p_i^t }...
Some Remarks on Boolean Sums (1979)
Summary Neciporuk, Lamagna/Savage and Tarjan determined the monotone network complexity of a set of Boolean sums if any two sums have at most one variable in common. Wegener then solved the case...
Codes: Unequal Probabilities, Unequal Letter Cost (1978)
Altenkamp, Doris, Mehlhorn, Kurt, Ausiello, Giorgio, Böhm, Corrado
A best possible bound for the weighted path length of binary search trees (1977)
The weighted path length of optimum binary search trees is bounded above by $\sum \beta_i + 2\sum \alpha_j + H$ where $H$ is the entropy of the frequency distribution, $\sum \beta _i $ is the total...
Van Wijngaarden Grammars and Space Complexity Class {EXSPACE} (1977)
Deussen, Peter, Mehlhorn, Kurt
Summary Top-down and bottom-up decision strategies for van Wijngaarden grammars led to type R and type L van Wijngaarden grammars. The corresponding language families are now shown to be equal...
Monotone Switching Circuits and Boolean Matrix Product (1976)
We explore the concept of local transformations of monotone switching circuits, i.e. what kind of local changes in a network leave the input/output behavior invariant. We obtain several general...
Binary Search Trees: Average and Worst Case Behavior (1976)
Güttler, Reiner, Mehlhorn, Kurt, Schneider, Wolfgang, Wernet, Norbert, Neuhold, Erich J.
9 by Springer-Verlag 1975 Nearly Optimal Binary Search Trees (1975)
Summary. We discuss two simple strategies for constructing binary search trees: "Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees...
Nearly Optimal Binary Search Trees (1975)
Summary We discuss two simple strategies for constructing binary search trees: Place the most frequently occurring name at the root of the tree, then proceed similary on the subtrees and choose...
Polynomial and Abstract Subrecursive Classes (1974)
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of...
Polynomial and Abstract Subrecursive Classes (1974)
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of...
Polynomial and Abstract Subrecursive Classes (1974)
We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of...
The "Almost All" Theory of Subrecursive Degrees is Decidable (1973)
We use constructive measure theory to show the decidability pf the "almost all" theory of subrecursive degrees. The formulas of this theory are built up using the constant 0 standing for the minimum...
The "Almost All" Theory of Subrecursive Degrees is Decidable (1973)
We use constructive measure theory to show the decidability pf the "almost all" theory of subrecursive degrees. The formulas of this theory are built up using the constant 0 standing for the minimum...
On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm
Kurt Mehlhorn And, Kurt Mehlhorn, Petra Mutzel
We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be...
On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm
We give a detailed description of the embedding phase of the Hopcroft and Tarjan planarity testing algorithm. The embedding phase runs in linear time. An implementation based on this paper can be...