Journallist

.

286: Kurt Mehlhorn.
Maximizing Nash Social Welfare in 2-Value Instances: A Simpler Proof for the Half-Integer Case, November 2024.
285: Mahyar Afshinmehr, Matin Ansaripour, Alireza Danaei, and Kurt Mehlhorn.
Approximate EFX and Exact tEFX Allocations for Indivisible Chores: Improved Algorithms.
CoRR, 2024.
284: Mahyar Afshinmehr, Mehrafarin Kazemi, and Kurt Mehlhorn.
MMS Approximations Under Additive Leveled Valuations.
CoRR, 2024.
283: Mahyar Afshinmehr, Alireza Danaei, Mehrafarin Kazemi, Kurt Mehlhorn, and Nidhi Rathi.
EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture.
CoRR, 2024.
282: Matin Ansaripour, Alireza Danaei, and Kurt Mehlhorn.
Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments.
CoRR, 2024.
281: Ioannis Caragiannis, Kurt Mehlhorn, and Nidhi Rathi.
Welfare-Optimal Serial Dictatorships have Polynomial Query Complexity.
CoRR, abs/2407.04474, 2024.
280: Frederic Folz, Kurt Mehlhorn, and Giovanna Morigi.
Self-organized transport in noisy dynamic networks.
Physical Review E, 110(4), 2024.
279: Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra.
Improving Envy Freeness up to Any Good Guarantees through Rainbow Cycle Number.
Mathematics of Operations Research, 2023.
a preliminary version of the paper was presented at EC '21 (https://doi.org/10.1145/3465456.3467605).
278: Hannaneh Akrami, Masoud Seddighin, Kurt Mehlhorn, and Golnoosh Shahkarami.
Randomized and Deterministic Maximin-share Approximations for Fractionally Subadditive Valuations.
In NeurIPS, 2023.
277: Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.
Satiation in Fisher Markets and Approximation of Nash Social Welfare.
Mathematics in Operations Research, 49:1109–1139, 2023.
276: Hannaneh Akrami, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta.
Fair and efficient allocation of indivisible chores with surplus.
In IJCAI, pages 2494–2502, 2023.
275: Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, and Ruta Mehta.
EFX Allocations: Simplifications and Improvements.
Operations Research, 2024.
preliminary version appeared in EC 2023.
274: Andreas Karrenbauer, Leonie Krull, Kurt Mehlhorn, Pranabendu Misra, Paolo Luigi Rinaldi, and Anna Twelsiek.
Improving Order with Queues, 2022.
273: Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, and Ernest van Wijland.
Maximizing Nash Social Welfare in 2-Value Instances: Delineating Tractability, 2022.
accepted to Mathematics of Operations Reseach, preliminary version in AAAI 2022.
272: Frederic Folz, Kurt Mehlhorn, and Giovanna Morigi.
Noise-induced network topologies.
PRL (Physical Review Letters), 130(26), 2023.
271: Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn.
Fair Division of Indivisible Goods for a Class of Concave Valuations.
Journal of Artificial Intelligence Research, 73:821 –, 2022.
a preliminary version appeared in FSTTCS 2018.
270: Hannaneh Akrami, Bhaskar Ray Chaudhury, Martin Hoefer, Kurt Mehlhorn, Marco Schmalhofer, Golnoosh Shahkarami, Giovanna Varricchio, Quentin Vermande, and Ernest van Wijland.
Maximizing Nash Social Welfare in 2-Value Instances.
In AAAI, 2022.
269: Frederic Folz, Kurt Mehlhorn, and Giovanna Morigi.
Interplay of periodic dynamics and noise: insights from a simple adaptive system.
Phys. Rev. E, 104, 2021.
268: Hannaneh Akrami, Bhaskar Ray Chaudhury, Kurt Mehlhorn, Golnoosh Shahkarami, and Quentin Vermande.
Nash Social Welfare for 2-value Instances, 2021.
superseeded by http://arxiv.org/abs/2107.08965.
267: Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta, and Pranabendu Misra.
Improving EFX Guarantees through Rainbow Cycle Number.
In EC '21, pages 310–311. ACM, 2021.
full paper to appear in Mathematics of Operations Research.
266: Vincenzo Bonifaci, Enrico Facca, Frederic Folz, Andreas Karrenbauer, Pavel Kolev, Kurt Mehlhorn, Giovanna Morigi, Golnoosh Shahkarami, and Quentin Vermande.
Physarum-Inspired Multi-Commodity Flow Dynamics.
Theoretical Computer Science, 920:1–20, 2022.
265: Dan Halperin, Sariel Har-Peled, Kurt Mehlhorn, Eunjin Oh, and Micha Sharir.
The Maximum-Level Vertex in an Arrangement of Lines.
Discrete and Computational Geometry, 67(2):439–461, 2022.
264: Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn.
EFX Exists for Three Agents.
JACM, 71:1–27, 2024.
a preliminary version appeared in EC '20.
263: Bhaskar Ray Chaudhury, Tellikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa.
A Little Charity Guarantees Almost Envy-Freeness.
SIAM J. Comput., 50(4):1336–1358, 2021.
262: Mohammad Abdulaziz, Kurt Mehlhorn, and Tobias Nipkow.
Trustworthy Graph Algorithms.
In MFCS 2019, volume 138 of LIPIcs, 2019.
261: Enrico Facca, Andreas Karrenbauer, Pavel Kolev, and Kurt Mehlhorn.
Convergence of the Non-Uniform Directed Physarum Dynamics.
Theor. Comput. Sci., 816:184–194, 2020.
260: Hannaneh Akrami, Kurt Mehlhorn, and Tommy Odland.
Ratio-Balanced Maximum Flows.
Inf. Process. Lett., 150:13–17, 2019.
259: Andreas Karrenbauer, Pavel Kolev, and Kurt Mehlhorn.
Convergence of the Non-Uniform Physarum Dynamics.
Theor. Comput. Sci., 816:260–269, 2020.
258: Ruben Becker, Vincenzo Bonifaci, Andreas Karrenbauer, Pavel Kolev, and Kurt Mehlhorn.
Two Results on Slime Mold Computations.
Theoretical Computer Science, 773:79–106, 2019.
257: Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.
Multi-finger binary search trees.
In ISAAC 2018, volume 123 of LIPIcs, pages 55:1–55:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
256: Bhaskar Ray Chaudhury and Kurt Mehlhorn.
Combinatorial Algorithms for General Linear Arrow-Debreu Markets.
In FSTTCS 2018, volume 122 of LIPIcs, pages 26:1–26:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
255: Bhaskar Ray Chaudhury, Yun Kuen Cheung, Jugal Garg, Naveen Garg, Martin Hoefer, and Kurt Mehlhorn.
On Fair Division of Indivisible Items.
In FSTTCS 2018, volume 122 of LIPIcs, pages 25:1–25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
254: Cosmina Croitoru and Kurt Mehlhorn.
On testing substituability.
Information Processing Letters, 138:19–21, 2018.
253: Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.
Earning limits in fisher markets with spending-constraint utilities.
In Algorithmic Game Theory - 10th International Symposium, SAGT 2017, L'Aquila, Italy, September 12-14, 2017, Proceedings, pages 67–79, 2017.
252: Przemysław Koprowski, Kurt Mehlhorn, and Saurabh Ray.
Corrigendum to “Faster Algorithms for Computing Hong's Bound on Absolute Positiveness [J. Symbolic Comput. 45(2010) 677-683]".
J. Symb. Comput., 87:238–241, 2018.
251: Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.
Approximating the Nash Social Welfare with Budget-Additive Valuations.
In SODA 2018, pages 2326–2340, 2018.
250: Michael Dirnberger and Kurt Mehlhorn.
Characterizing networks formed by P. polycephalum.
J. Phys. D: Appl. Phys., 50(22), 2017.
249: Michael Dirnberger, Kurt Mehlhorn, and Tim Mehlhorn.
Introducing the slime mold graph repository.
Journal of Physics D: Applied Physics, 60(26), 2017.
248: Pavel Kolev and Kurt Mehlhorn.
A Note on Spectral Clustering.
In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pages 57:1–57:14, 2016.
247: Xiaohui Bei, Jugal Garg, Martin Hoefer, and Kurt Mehlhorn.
Earning and Utility Limits in Fisher Markets.
ACM Trans. Economics and Comput., 7(2):10:1–10:35, 2019.
246: Omar Darwish and Kurt Mehlhorn.
Improved Balanced Flow Computation Using Parametric Flow.
Information Processing Letters, pages 560–563, 2016.
245: Ran Duan, Jugal Garg, and Kurt Mehlhorn.
An improved combinatorial algorithm for linear Arrow-Debreu markets.
In SODA, pages 90–106, 2016.
244: Cosmina Croitoru and Kurt Mehlhorn.
Opposition frameworks.
In Logics in Artificial Intelligence - 15th European Conference, JELIA 2016, Larnaca, Cyprus, November 9-11, 2016, Proceedings, pages 190–206, 2016.
243: Kurt Mehlhorn and Sanjeev Saxena.
A still simpler way of introducing the interior-point method for linear programming.
Computer Science Review, 22:1–11, 2016.
242: Cristian Calude, editor.
The Human Face of Computing, chapter Kurt Mehlhorn: From Theory to Library of Efficient Data Types and Algorithms (LEDA) and Algorithm Engineering, pages 59–72.
Imperical College Press, 2015.
241: Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.
Pattern-avoiding access in binary search trees.
In FOCS, pages 410–423, 2015.
240: Khaled M. Elbassioni, Kurt Mehlhorn, and Fahimeh Ramezani.
Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design.
Theory Comput. Syst., 59(4):641–663, 2016.
239: Kurt Mehlhorn.
On the implementation of combinatorial algorithms for the linear exchange market.
In Christos Zaroliagis, Grammati Pantziou, and Spyros Kontogiannis, editors, Algorithms, Probability, Networks, and Games, volume 9295 of Lecture Notes in Computer Science, pages 87–94. Springer International Publishing, 2015.
238: Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.
Self-Adjusting Binary Search Trees: What Makes Them Tick?.
In Algorithms – ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 300–312. Springer Berlin Heidelberg, 2015.
237: Kurt Mehlhorn.
Algorithms and Programs: The 2014 Erasmus Lecture.
European Review, pages 4–16, 2016.
236: Parinya Chalermsook, Mayank Goswami, László Kozma, Kurt Mehlhorn, and Thatchaphol Saranurak.
Greedy is an Almost Optimal Deque.
In WADS 2015, LNCS, March 2015.
235: Lars Noschinski, Christine Rizkallah, and Kurt Mehlhorn.
Verification of certifying computations through AutoCorres and Simpl.
In NASA Formal Methods, volume 8430 of Lecture Notes in Computer Science, pages 46–61. Springer, 2014.
234: Tomasz Jurkiewicz, Kurt Mehlhorn, and Patrick Nicholson.
Cache-Oblivious VAT-Algorithms.
April 2014.
233: Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, and Adrian Neumann.
New Approximability Results for the Robust k-Median Problem.
In Algorithm Theory — SWAT 2014, volume 8503 of Lecture Notes in Computer Science, pages 50–61, 2014.
232: Michael Sagraloff and Kurt Mehlhorn.
Computing Real Roots of Real Polynomials – An Efficient Method Based on Descartes' Rule of Signs and Newton Iteration.
J. Symb. Comput. (JSC), 73:46–86, 2016.
231: Luca Becchetti, Vincenzo Bonifaci, Michael Dirnberger, Andreas Karrenbauer, and Kurt Mehlhorn.
Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds.
In ICALP, volume 7966 of LNCS, pages 472–483, 2013.
Erratum.
230: Kurt Mehlhorn, Michael Sagraloff, and Pengming Wang.
From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition.
J. Symb. Comput. (JSC), 66:34–69, 2015.
preliminary version in ISSAC 2013, pages 283 - 290.
229: Khaled Elbassioni, Kazuhisa Makino, Kurt Mehlhorn, and Fahimeh Ramezani.
On Randomized Fictitious Play for Approximating Saddle Points Over Convex Sets.
Algorithmica, 73(2):441–459, 2015.
a preliminary version appeared in COCOON 2013.
228: Chien-Chung Huang, Telikepalli Kavitha, Kurt Mehlhorn, and Dimitrios Michail.
Fair matchings and related problems.
Algorithmica, 74(3):1184–1203, 2016.
227: Ran Duan and Kurt Mehlhorn.
A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market.
Information and Computation, 243:112–132, 2015.
a preliminary version appeared in ICALP 2013, LNCS 7965, pages 425-436.
226: Kurt Mehlhorn, Adrian Neumann, and Jens M. Schmidt.
Certifying 3-Edge-Connectivity.
Algorithmica, 77(2):309–335, 2017.
A preliminary version appeared in Graph-Theoretic Concepts in Computer Science 2013, LNCS 8165, 358 – 369.
225: E. Alkassar, S. Böhme, K. Mehlhorn, and Ch. Rizkallah.
A Framework for the Verification of Certifying Computations.
Journal of Automated Reasoning (JAR), 52(3):241–273, 2014.
A preliminary version appeared under the title “Verification of Certifying Computations” in CAV 2011, LCNS Vol 6806, pages 67 – 82.
224: Tomasz Jurkiewicz and Kurt Mehlhorn.
The Cost of Address Translation.
In ALENEX, pages 148–162, 2013.
full paper to appear in Journal of Experimental Algorithmics (JEA).
223: Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Kasper Green Larsen, Kurt Mehlhorn, and Carola Winzen.
The Query Complexity of a Permutation-Based Variant of Mastermind.
Discrete Applied Mathematics, pages 28–50, 2019.
222: Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun.
Counting Arbitrary Subgraphs in Data Streams.
In ICALP 2012, volume 7392 of LNCS, pages 598–609, 2012.
221: Karl Bringmann, Kurt Mehlhorn, and Adrian Neumann.
Remarks on Category-Based Routing in Social Networks.
February 2012.
220: E. Amaldi, C. Iuliano, T. Jurkiewicz, K. Mehlhorn, and R. Rizzi.
Improved minimum cycle bases algorithms by restriction to isometric cycles.
A preliminary version of this work appeared in ESA 2009, volume 5757 of LNCS, pages 301-312, August 2011.
219: Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun.
Approximate Counting of Cycles in Streams.
In ESA 2011, volume 6942 of LNCS, pages 677–688, 2011.
218: Vincenzo Bonifaci, Kurt Mehlhorn, and Girish Varma.
Physarum can compute shortest paths.
Journal of Theoretical Biology, 309(0):121–133, 2012.
A preliminary version of this paper appeared at SODA 2012 (pages 233-240).
217: Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer.
Online Graph Exploration: New Results on Old and New Algorithms.
Theoretical Computer Science, pages 62–72, 2012.
preliminary version appeared in ICALP 2011, LNCS 6756, 478 – 489.
216: E. Alkassar, S. Böhme, K. Mehlhorn, and Ch. Rizkallah.
Verification of Certifying Computations.
In Computer Aided Verification (CAV), volume 6806 of LNCS, pages 67–82, 2011.
full paper available at http://arxiv.org/abs/1301.7462.
215: Giorgos Christodoulou, Kurt Mehlhorn, and Evangelia Pyrga.
Improving the Price of Anarchy for Selfish Routing via Coordination Mechanisms.
Algorithmica, 69(3):619–640, 2014.
214: R.M. McConnell, K. Mehlhorn, S. Näher, and P. Schweitzer.
Certifying algorithms.
Computer Science Review, 5(2):119–161, 2011.
213: N. Shervashidze, P. Schweitzer, E.J. van Leeuwen, K. Mehlhorn, and K.M. Borgwardt.
Weisfeiler-Lehman Graph Kernels.
Journal of Machine Learning Research (JMLR), 12:2539–2561, 2011.
212: Kurt Mehlhorn and Pascal Schweitzer.
Progress on Certifying Algorithms.
In FAW, volume 6213 of Lecture Notes in Computer Science, pages 1–5, 2010.
211: A. Elmasry, K. Mehlhorn, and J. M. Schmidt.
A Linear Time Certifying Triconnectivity Algorithm for Hamiltonian Graphs.
Algorithmica, 62(3):754–766, 2012.
210: A. Elmasry, K. Mehlhorn, and J. M. Schmidt.
Every DFS-Tree of a 3-Connected Graph Contains a Contractible Edge.
Journal of Graph Theory, 72(1):112–121, 2013.
209: K. Mehlhorn, R. Osbild, and M. Sagraloff.
A General Approach to the Analysis of Controlled Perturbation Algorithms.
Computational Geometry, 44(9):507–528, 2011.
208: A. Eigenwillig and K. Mehlhorn.
Multiplication of Long Integers(Faster than Long Multiplication).
English translation of Paper 196, to appear in English version of “Taschenbuch der Algorithmen”.
207: Kurt Mehlhorn and Saurabh Ray.
Faster algorithms for computing Hong's bound on absolute positiveness.
J. Symb. Comput., 45(6):677–683, 2010.
206: T. Kavitha, Ch. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, and K. Zweig.
Cycle Bases in Graphs: Characterization, Algorithms, Complexity, and Applications.
Computer Science Review, 3:199–243, 2009.
205: N. Shervashidze, S.V.N. Vishwanathan, T.H. Petri, K. Mehlhorn, and K.M. Borgwardt.
Efficient Graphlet Kernels for Large Graph Comparison.
In 12th International Conference on Artificial Intelligence and Statistics (AISTATS), 2009.
204: Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn, and Ron Wein.
Arrangements on parametric surfaces i: General framework and infrastructure.
Mathematics in Computer Science, 4:45–66, 2010.
10.1007/s11786-010-0042-5.
203: N. Garg, T. Kavitha, A. Kumar, K. Mehlhorn, and J. Mestre.
Assigning Papers to Referees.
Algorithmica, 58(1):119–136, 2010.
202: Kurt Mehlhorn and Michael Sagraloff.
A Deterministic Descartes Algorithm for Real Polynomials.
Journal of Symbolic Computation, 46(1):70 – 90, 2011.
A preliminary version appeared in ISSAC 2009.
201: R. Hariharan, T. Kavitha, and K. Mehlhorn.
Faster Deterministic and Randomized Algorithms for Minimum Cycle Basis in Directed Graphs.
SIAM Journal of Computing, 38(4):1430–1447, 2008.
200: Kurt Mehlhorn, Stefan Näher, and Peter Sanders.
Engineering DFS-based graph algorithms.
arXiv preprint arXiv:1703.10023, 2017.
199: T. Kavitha and K. Mehlhorn.
Algorithms to Compute Minimum Cycle Basis in Directed Graphs.
Theory of Computing Systems, 40(4):485–505, 2007.
a preliminary version of this paper appeared in STACS 2005.
198: E. Berberich, E. Fogel, D. Halperin, K. Mehlhorn, and R. Wein.
Sweeping and Maintaining Two-Dimensional Arrangement on Surfaces: A First Step.
In ESA, volume 4698 of LNCS, pages 645–656, 2007.
197: P. Hachenberger, L. Kettner, and K. Mehlhorn.
Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments.
CGTA, 38:64–99, 2007.
196: A. Eigenwillig and K. Mehlhorn.
Multiplikation langer Zahlen (schneller als in der Schule).
In H. Alt and B. Voecking, editors, Taschenbuch der Algorithmen. Springer Verlag, 2007.
195: K. Mehlhorn and D. Michail.
Minimum Cycle Bases: Faster and Simpler.
ACM Transactions on Algorithms, 6(1), 2009.
194: D. Abraham, R. Irving, T. Kavitha, and K. Mehlhorn.
Popular Matchings.
Siam Journal of Computing, 37(4):1030–1045, 2007.
a prelimary version appeared in SODA 2005, pages 424 – 432.
193: T. Kavitha, K. Mehlhorn, and D. Michail.
New Approximation Algorithms for Minimum Cycle Bases of Graphs.
Algorithmica, 59(4):471–488, 2011.
a preliminary version of this paper appeared in STACS 2007.
192: K. Mehlhorn, R. Osbild, and M. Sagraloff.
Reliable and Efficient Computational Geometry via Controlled Perturbation.
In ICALP, volume 4051 of LNCS, pages 299–310, 2006.
191: C. Gotsman, K. Kaligosi, K. Mehlhorn, D. Michail, and E. Pyrga.
Cycle Basis of Graphs and Sampled Manifolds.
Computer Aided Geometric Construction, 24:464–480, 2007.
190: E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Schömer, and N. Wolpert.
EXACUS—Efficient and Exact Algorithms for Curves and Surfaces.
In ESA, volume 3669 of LNCS, pages 155–166, 2005.
189: R. Hariharan, T. Kavitha, and K. Mehlhorn.
A Faster Deterministic Algorithm for Minimum Cycle Basis in Directed Graphs.
In ICALP, volume 4051 of LNCS, pages 250–261, 2006.
188: K. Kaligosi, K. Mehlhorn, J. I. Munro, and P.Sanders.
Towards Optimal Multiple Selection.
In ICALP, volume 3580 of LNCS, pages 103–114, 2005.
187: A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, and N. Wolpert.
An Exact Descartes Algorithm with Approximate Coefficients (Extended Abstract).
In CASC, volume 3718 of LNCS, pages 138–149, 2005.
186: K. Mehlhorn and D. Michail.
Implementing Minimum Cycle Basis Algorithms.
ACM Journal of Experimental Algorithms, 11, 2006.
preliminary version in WEA 2005, LNCS Vol. 3503, pages 32-43.
185: W. Krandick and K. Mehlhorn.
New Bounds for the Descartes Method.
Journal of Symbolic Computation, 41(1):49–66, 2006.
184: T. Kavitha and K. Mehlhorn.
Algorithms to Compute Minimum Cycle Basis in Directed Graphs.
In STACS, volume 3404 of LNCS, pages 654–665, 2005.
183: S. Funke, Ch. Klein, K. Mehlhorn, and S. Schmitt.
Controlled Perturbation for Delaunay Triangulations.
In SODA, pages 1047–1056, 2005.
182: D. Abraham, R. Irving, T. Kavitha, and K. Mehlhorn.
Popular Matchings.
In SODA, pages 424–432, 2005.
181: D. Abraham, K. Cechlárová D. Manlove, and K. Mehlhorn.
Pareto-optimality in house allocation problems.
In ISAAC, volume 3341 of LNCS, pages 3–15, 2004.
180: K. Mehlhorn and D. Michail.
Network Problems with Non-Polynomial Weights and Applications.
179: S. Baswana, T. Kavitha, K. Mehlhorn, and S. Pettie.
Efficient Construction of $(\alpha,\beta)$ -Spanners and Purely Additive Spanners.
In SODA, pages 672–681, 2005.
178: T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch.
An $\tilde{O}(m^2n)$ Algorithm for Minimum Cycle Bases of Graphs.
Algorithmica, 52:222–349, 2008.
preliminary version in ICALP 2004, LNCS Volume 3142, pages 846–857.
177: L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, and C. Yap.
Classroom Examples of Robustness Problems in Geometric Computations.
Computational Geometry: Theory and Applications (CGTA), 40:61–78, 2008.
a preliminary version appeared in ESA 2004, LNCS 3221, pages 702 – 713.
176: B. Aranov, T. Asano, N. Katoh, K. Mehlhorn, and T. Tokuyama.
Polyline Fitting of Planar Points under Min-Sum Criteria.
In ISAAC, volume 3341 of LNCS, pages 77–88, 2004.
175: T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch.
Strongly Stable Matchings in Time .
In STACS, volume 2996 of LNCS, pages 222–233, 2004.
full version to appear in TALG.
174: H. Bast, K. Mehlhorn, G. Schäfer, and H.Tamaki.
Matching Algorithms are Fast in Sparse Random Graphs.
Theory of Computing Systems, 31(1):3–14, 2005.
preliminary version in STACS 2004, LNCS 2996, 81 – 92.
173: E. Althaus, F. Eisenbrand, S. Funke, and K. Mehlhorn.
Point Containment in the Integer Hull of a Polyhedron.
In SODA, pages 929–933, 2004.
172: R. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. Paluch.
Rank-Maximal Matchings.
ACM Transactions on Algorithms, 2(4):1–9, 2006.
a preliminary version appeared in SODA 2004, pages 68 – 75.
171: C. Banderier, K. Mehlhorn, and R. Beier.
Smoothed Analyis of Three Combinatorial Problems.
In MFCS, pages 198–207, 2003.
170: M. Granados, P. Hachenberger, S. Hert, L. Kettner, K. Mehlhorn, and M. Seel.
Boolean Operations on 3D Selective Nef Complexes, Data Structure, Algorithms, and Implementation.
In ESA, volume 2832 of LNCS, pages 654–666, 2003.
169: K. Mehlhorn.
The Reliable Algorithmic Software Challenge (RASC).
In Computer Science in Perspective, volume 2598 of LNCS, pages 255–263, 2003.
168: M. Dhiflaoui, S. Funke, C. Kwappik, K. Mehlhorn, M. Seel, E. Schömer, R. Schulte, and D. Weber.
Certifying and Repairing Solutions to Large LPs, How Good are LP-solvers?.
In SODA, pages 255–256, 2003.
167: E. Althaus, A. Bockmayr, M. Elf, T. Kasper, M. Jünger, and Kurt Mehlhorn.
SCIL – Symbolic Constraints in Integer Linear Programming.
In ESA, volume 2461 of LNCS, pages 75–87. Springer, 2002.
166: K. Mehlhorn and U. Meyer.
External memory breadth-first search with sublinear I/O.
In 10th European Symposium on Algorithms, volume 2461 of Lecture Notes in Computer Science, pages 723–735. Springer, 2002.
165: E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, and E. Schömer.
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons.
In ESA, volume 2461 of LNCS, pages 174–186, 2002.
164: D. Kratsch, R. McConnell, K. Mehlhorn, and J. Spinrad.
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs.
SIAM J. Comput., 36(2):326–353, 2006.
preliminary version in SODA 2003, pages 158–167.
163: K. Mehlhorn.
A Remark on the Sign Variation Method for Real Root Isolation.
2001.
162: St. Kwek and K. Mehlhorn.
Optimal Search for Rationals.
Information Processing Letters, 86:23 – 26, 2003.
161: H. Bast, K. Mehlhorn, G. Schäfer, and H.Tamaki.
A Heuristic for Dijkstra's Algorithm with Many Targets and its Use in Weighted Matching Algorithms.
Algorithmica, pages 75–88, 2003.
160: K. Mehlhorn.
From Algorithm to Program to Software Library.
In Reinhard Wilhelm, editor, Informatics - 10 Years Back. 10 Years Ahead., volume 2000 of Lecture Notes in Computer Science, pages 268–273. Springer, 2001.
159: K. Mehlhorn and M. Ziegelmann.
CNOP - A Package for Constrained Network Optimization.
In ALENEX 01, volume 2153 of Lecture Notes in Computer Science, pages 17–31, 2001.
158: John D. Kececioglu, Hans-Peter Lenhof, Kurt Mehlhorn, Petra Mutzel, Knut Reinert, and Martin Vingron.
A polyhedral approach to sequence alignment problems.
Discrete Applied Mathematics, 104(1-3):143–186, 2000.
157: K. Mehlhorn and M. Seel.
Infimaximal Frames: A Technique for Making Lines look like Segments.
Journal of Computational Geometry & Applications, 13(3):241–255, 2003.
156: K. Mehlhorn, V. Priebe, G. Schäfer, and N. Sivadasan.
All-pairs shortest-paths computation in the presence of negative cycles.
Information Processing Letters, 81(6):341–343, 2002.
155: C. Burnikel, S. Funke, K. Mehlhorn, S. Schirra, and S. Schmitt.
A Separation Bound for Real Algebraic Expressions.
Algorithmica, 55(1):14–28, 2009.
a preliminary version appeared in ESA 2001, LNCS 2161, pages 254–265.
154: K. Mehlhorn and G. Schäfer.
Implementation of Weighted Matchings in General Graphs: The Power of Data Structures.
ACM Journal of Experimental Algorithmics, 7, 2002.
153: K. Mehlhorn and M. Ziegelmann.
Resource constrained shortest paths.
In 8th European Symposium on Algorithms, volume 1879 of Lecture Notes in Computer Science, pages 326–337, 2000.
152: K. Mehlhorn.
Constraint Programming and Graph Algorithms.
In ICALP 2000, Lecture Notes in Computer Science, 2000.
slides.
151: Alexander Koller, Kurt Mehlhorn, and Joachim Niehren.
A Polynomial-Time Fragment of Dominance Constraints.
In Proceedings of the 38th ACL, Hong Kong, 2000.
150: E. Althaus, D. Duchier, A. Koller, K. Mehlhorn, J. Niehren, and S. Thiel.
An Efficient Graph Algorithm for Dominance Constraints.
Algorithmica, 48:194–219, 2003.
a preliminiary version appreared in SODA 2001.
149: S. Funke and K. Mehlhorn.
LOOK, A Lazy Object-Oriented Kernel for Geometric Computations.
Computational Geometry: Theory and Applications, 22:99–118, 2002.
148: K. Mehlhorn and Sven Thiel.
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint.
In Sixth International Conference on Principles and Practice of Constraint Programming (CP2000), volume 1894 of Lecture Notes in Computer Science, 2000.
147: K. Mehlhorn and P. Sanders.
Scanning Multiple Sequences Via Cache Memory.
Algorithmica, 35(1):75–93, 2003.
146: K. Mehlhorn and S. Schirra.
Geometric Computing with CGAL and LEDA.
In P.-J. Laurenat, P. Sablonnière, and Larry L. Schumaker, editors, Curve and Surface Design: Saint-Malo 1999, pages 277–286. Vanderbilt University Press, 2000.
145: K. Mehlhorn and St. Schirra.
Exact Computation with leda_real - Theory and Geometric Applications.
In G. Alefeld, J. Rohn, S. Rumpf, and T. Yamamoto, editors, Symbolic Algebraic Methods and Verification Methods. Springer Verlag, Vienna, 2001.
144: E. Althaus, K. Mehlhorn, S. Näher, and S. Schirra.
Experiments on Curve Reconstruction.
In ALENEX, pages 103–114, 2000.
143: Ernst Althaus and Kurt Mehlhorn.
Traveling Salesman-Based Curve Reconstruction in Polynomial Time.
SIAM Journal on Computing, 31(1):27–66, February 2002.
142: Stefan Funke, Kurt Mehlhorn, and Stefan Naeher.
Structural Filtering: A Paradigm for Efficient and Exact Geometric Algorithms.
In Proceedings of the 11th Canadian Conference on Computational Geometry, pages 39–46, 2005.
141: S. Arikati and K. Mehlhorn.
A Correctness Certificate for the Stoer-Wagner Mincut Algorithm.
Information Processing Letters, 70:251–254, 1999.
140: J. Cheriyan and K. Mehlhorn.
An Analysis of the Highest-Level Selection Rule in the Preflow-Push Max-Flow Algorithm.
IPL, 69:239–242, 1999.
139: T.K. Dey, K. Mehlhorn, and E.A. Ramos.
Curve Reconstruction: Connecting Dots with Good Reason.
Computational Geometry: Theory and Applications, 15(4):229–244, 2000.
138: A. Crauser and K. Mehlhorn.
LEDA-SM, extending LEDA to Secondary Memory.
In WAE 99, Lecture Notes in Computer Science, pages 228–242, 1999.
137: K. Mehlhorn, M. Müller, S. Näher, S. S. Schirra, M. Seel, C. Uhrig, and J. Ziegler.
A computational basis for higher-dimensional computational geometry and its applications.
Computational Geometry: Theory and Applications, 10:289–303, 1998.
136: A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders.
A Parallelization of Dijkstra's Shortest Path Algorithm.
Lecture Notes in Computer Science, 1450:722–??, 1998.
135: C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
Efficient Exact Computational Geometry Made Easy.
In Proceedings of the 15th Annual Symposium on Computational Geometry (SCG'99), pages 341–350, 1999.
134: K. Mehlhorn and S. Näher.
From Algorithms to Working Programs: On the Use of Program Checking in LEDA.
In MFCS'98, volume 1450 of LNCS, pages 84–93, 1998.
133: A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E.A. Ramos.
Randomized External-Memory Algorithms for Some Geometric Problems.
In Proceedings of the 14th Annual ACM Symposium on Computational Geometry (SCG'98), 1998.
132: E. Althaus and K. Mehlhorn.
Maximum Network Flow with Floating Point Arithmetic.
Information Processing Letters, 66:109–113, 1998.
131: U. Finkler and K. Mehlhorn.
Checking Priority Queues.
In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 901–902, 1999.
130: K. Mehlhorn, S. Näher, and C. Uhrig.
The LEDA Platform for Combinatorial and Geometric Computing.
In Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP'97), volume 1256 of Lecture Notes in Computer Science, pages 7–16, 1997.
129: A. Crauser, K. Mehlhorn, and U. Meyer.
Kürzeste-Wege-Berechnung bei sehr großen Datenmengen.
Promotion tut not: Innovationsmotor “Graduiertenkolleg", Aachener Beiträge, pages 113–132, 1997.
128: C. Cooper, A. Frieze, K. Mehlhorn, and V. Priebe.
Average-case complexity of shortest-paths problems in the vertex-potential model.
In José Rolim, editor, Proceedings of the International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM`97), volume 1269 of Lecture Notes in Computer Science, pages 15–26. Springer, 1997.
full papeer to appear in “Random Structures and Algorithms, RSA 16 (2000) 33-46”.
127: C. Burnikel, R. Fleischer, K. Mehlhorn, and S. Schirra.
A Strong and Easily Computable Separation Bound for Arithmetic Expressions Involving Radicals.
Algorithmica, 27:87–99, 2000.
126: K. Mehlhorn, T. C. Shermer, and C.-K. Yap.
A Complete Roundness Classification Procedure.
In Proceedings of the 13th Annual ACM Symposium on Computational Geometry (SCG'97), pages 129–138, 1997.
125: K. Reinert, H.-P. Lenhof, P. Mutzel, K. Mehlhorn, and J.D. Kececioglu.
A Branch-And-Cut Algorithm for Multiple Sequence Alignment.
In Proceedings of the First International Conference on Computational Molecular Biology, pages 241–250, New York, January19–22 1997. ACM Press.
124: K. Mehlhorn and V. Priebe.
On the All-Pairs Shortes Path Algorithm of Moffat and Takaoka.
Random Structures &Algorithms, 10:205–220, 1997.
123: U. Finkler and K. Mehlhorn.
Runtime Prediction of Real Programs on Real Machines.
In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97), pages 380–389, 1997.
122: J. Cheriyan and K. Mehlhorn.
Algorithms for dense graphs and networks.
Algorithmica, 15(6):521–549, 1996.
121: S. Arya, M.J. Golin, and K. Mehlhorn.
On the Expected Depth of Random Circuits.
Combinatorics, Probability, and Computing, 8:209–228, 1999.
120: K. Mehlhorn.
Amortisierte Analyse.
In Th. Ottmann, editor, Prinzipien des Algorithmenentwurfs, pages 91–102. Spektrum Lehrbuch, 1998.
119: J. Cheriyan, T. Hagerup, and K. Mehlhorn.
An -Time Maximum Flow Algorithm.
SIAM Journal of Computing, 25(6):1144–1170, 1996.
118: Kurt Mehlhorn, Stefan Näher, Michael Seel, Raimund Seidel, Thomas Schilz, Stefan Schirra, and Christian Uhrig.
Checking geometric programs or verification of geometric structures.
Computational Geometry, 12(1-2):85–103, 1999.
preliminary version in SoCG 96.
117: C. Burnikel, J. Könemann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig.
Exact Geometric Computation in LEDA.
In Proceedings of the 11th Annual Symposium on Computational Geometry (SCG'95), pages C18–C19, New York, NY, USA, June 1995. ACM Press.
116: K. Mehlhorn and S. Näher.
LEDA: A Platform for Combinatorial and Geometric Computing.
Communications of the ACM, 38(1):96–102, 1995.
115: K. Mehlhorn.
Experiences with the Implementation of Geometric Algorithms.
In Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, and Nicola Santoro, editors, Proceedings of the 4th International Workshop on Algorithms and Data Structures (WADS'95), volume 955 of Lecture Notes in Computer Science, pages 518–518. Springer, August 1995.
114: K. Mehlhorn and V. Priebe.
On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka.
In Proceedings of the 3rd Annual European Symposium (ESA'95), volume 979 of Lecture Notes in Computer Science, pages 185–198. Springer, 1995.
113: C. Burnikel, K. Mehlhorn, and S. Schirra.
How to compute the Voronoi diagram of line segments: Theoretical and experimental results.
In ESA, volume 855 of Lecture Notes in Computer Science, pages 227–239, 1994.
112: K. Mehlhorn and S. Näher.
The Implementation of Geometric Algorithms.
In IFIP Transactions A-51, “Technology and Foundations”, Information Processing`94, Vol. I, pages 223–231, 1994.
111: K. Mehlhorn and P. Mutzel.
On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm.
Algorithmica, 16(2):233–242, 1995.
110: K. Mehlhorn, P. Mutzel, and S. Näher.
An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm.
Technical Report MPI-I-93-151, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1993.
109: C. Burnikel, K. Mehlhorn, and S. Schirra.
On Degeneracy in Geometric Computations.
In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94), pages 16–23, 1994.
108: G. Bilardi, S. Chaudhuri, D. Dubhashi, and K. Mehlhorn.
A Lower Bound for Area–Universal Graphs.
Information Processing Letters, 51(2):101–106, 1994.
107: K. Dobrindt, K. Mehlhorn, and M. Yvinec.
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron.
In Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro, and Sue Whitesides, editors, Proceedings of the 3rd International Workshop on Algorithms and Data Structures (WADS'93), volume 709 of Lecture Notes in Computer Science, pages 314–324, Montréal, Canada, 11–13 August 1993. Springer.
106: D. Dubhashi, K. Mehlhorn, D. Ranjan, and C. Thiel.
Searching, Sorting, and Randomized Algorithms for Central Elements and Ideal Counting in Posets.
In Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'93), volume 761 of Lecture Notes in Computer Science, pages 436–443. Springer, 1993.
105: R. Klein, K. Mehlhorn, and S. Meiser.
Randomized Incremental Construction of Abstract Voronoi Diagrams.
Computational Geometry: Theory and Applications, 3:157–184, 1993.
104: K. Mehlhorn, R. Sundar, and C. Uhrig.
Maintaining Dynamic Sequences under Equality Tests in Polylogarithmic Time.
Algorithmica, 17(2):183–198, 1997.
103: T. Hagerup, K. Mehlhorn, and I. Munro.
Optimal Algorithms for Generating Discrete Random Variables with Changing Distributions.
In Proceedings of International Conference on Automata, Language, and Programming (ICALP'93), volume 700 of Lecture Notes in Computer Science, pages 253–264. Springer, 1993.
102: K. Mehlhorn and S. Näher.
Algorithm Design and Software Libraries: Recent Developments in the LEDA Project.
In Jan van Leeuwen, editor, Proceedings of the IFIP 12th World Computer Congress. Volume 1: Algorithms, Software, Architecture, pages 493–508. Elsevier, September 1992.
101: L. Kučera, K. Mehlhorn, B. Preis, and E. Schwarzenecker.
Exact Algorithms for a Geometric Packing Problem (extended abstract).
In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS'93), volume 665 of Lecture Notes in Computer Science, pages 317–322. Springer, 1993.
100: K. Mehlhorn, S. Meiser, and R. Rasch.
Furthest Site Abstract Voronoi Diagrams.
International Journal of Computational Geometry and Applications, 11(6):583 – 616, 2001.
99: C. Burnikel, K. Mehlhorn, and S. Schirra.
The LEDA Class real Number.
Technical Report MPI-I-96-1-001, Max-Planck-Institut für Informatik, Saarbrücken, 1996.
98: P. Dietz, K. Mehlhorn, R. Raman, and C. Uhrig.
Lower Bounds for Set Intersection Queries.
Algorithmica, 14(2):154–168, August 1995.
97: K. Mehlhorn and S. Näher.
Algorithm Design and Software Libraries: Recent Developments in the LEDA Project.
In IFIP Transactions: “Algorithms, Software, Architecture”, Information Processing 92, Vol. I, pages 493–505, 1992.
96: M. Kaufmann and K. Mehlhorn.
On Local Routing of Two–Terminal Nets.
Journal on Combinatorial Theory B, 55:33–72, 1992.
95: H. Alt, L. Guibas, R. Karp, K. Mehlhorn, and A. Widgerson.
A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.
Algorithmica, 16(4/5):543–547, 1996.
94: H. Alt, V. Geffert, and K. Mehlhorn.
A Lower Bound for the Nondeterministic Space Complexity of Contextfree Recognition.
Information Processing Letters, 42:25–27, 1992.
93: Hanna Baumgarten, Hermann Jung, and Kurt Mehlhorn.
Dynamic Point Location in General Subdivisions.
Journal of Algorithms, 17(3):342–380, 1994.
92: K. Clarkson, K. Mehlhorn, and R. Seidel.
Four Results on Randomized Incremental Constructions.
Computational Geometry: Theory and Applications, 3:185–212, 1993.
91: K. Mehlhorn, M. Sharir, and E. Welzl.
Tail Estimates for the Efficiency of Randomized Incremental Algorithms for Line Segment Intersection.
Computational Geometry: Theory and Applications, 3:235–246, 1993.
90: H. Alt, N. Blum, K. Mehlhorn, and M. Paul.
Computing a Maximum Cardinality Matching in a Bipartite Graph in Time $O(n^{1.5}\sqrt{m/\log n})$ .
Information Processing Letters, 37:237–240, 1991.
89: K. Mehlhorn and S. Näher.
Bounded Ordered Dictionaries in $O(\log \log N)$ Time and Space.
Information Processing Letters, 35:183–189, 1990.
88: S. Näher and K. Mehlhorn.
LEDA: A Library of Efficient Data Types and Algorithms.
In ICALP'90, volume 443 of Lecture Notes in Computer Science, pages 1–5. Springer, 1990.
87: K. Mehlhorn, S. Näher, and C. Uhrig.
Hidden Line Elimination for Isooriented Rectangles.
Information Processing Letters, 35:137–143, 1990.
86: H. Alt, R. Fleischer, M. Kaufmann, K. Mehlhorn, S. Näher, S. Schirra, and C. Uhrig.
Approximate Motion Planning and the Complexity of the Boundary of the Union of Simple Geometric Figures.
Algorithmica, 8(5/6):391–406, 1992.
85: R. Fleischer, K. Mehlhorn, G. Rote, E. Welzl, and C.-K. Yap.
Simultaneous Inner and Outer Approximation of Shapes.
Algorithmica, 8(5/6):365–389, 1992.
84: R. Fleischer, H. Jung, and K. Mehlhorn.
A Communication-Randomness Tradeoff for Two-processor Systems.
Information and Computation, 116(2):155–161, 1995.
83: K. Mehlhorn and A. Tsakalidis.
Data Structures.
In Handbook of Theoretical Computer Science, pages 303–341. Elsevier Science Publishers, 1990.
82: J. Cheriyan, T. Hagerup, and K. Mehlhorn.
Can a Maximum Flow be Computed in Time?.
In Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP'90), volume 443 of Lecture Notes in Computer Science, pages 235–248. Springer, 1990.
81: K. Mehlhorn and S. Näher.
LEDA: A Library of Efficient Data Types and Algorithms.
In MFCS'89, volume 379 of Lecture Notes in Computer Science, pages 88–106, 1989.
80: K. Mehlhorn, S. Näher, and M. Rauch.
On the Complexity of a Game Related to the Dictionary Problem.
SIAM Journal of Computing, 19(5):902–906, 1990.
79: K. Mehlhorn, C. O'Dúnlaing, and S. Meiser.
On the Construction of Abstract Voronoi Diagrams.
Discrete and Computational Geometry, 6(3):211–224, 1991.
78: M. Kaufmann and K. Mehlhorn.
Routing Problems in Grid Graphs.
In L. Korte and S. Prömel, editors, Paths, Flows, and VLSI Layout, volume 9, chapter Algorithms and Combinatorics. Springer, 1990.
77: M. Kaufmann and K. Mehlhorn.
A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs.
SIAM Journal of Computing, 23(2):227–246, 1994.
76: Y.T. Ching, K. Mehlhorn, and M. Smid.
Dynamic Deferred Data Structuring.
Information Processing Letters, 35:37–40, 1990.
75: K. Mehlhorn, W.J. Paul, and C. Uhrig.
Versus Index Registers and Modifiable Versus Non-modifiable Programs.
Information and Computation, 101:123–129, 1992.
74: M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan.
Dynamic perfect hashing: Upper and lower bounds.
SIAM Journal of Computing, 23(4):738–761, 1994.
73: S. Gao, M. Jerrum, M. Kaufmann, K. Mehlhorn, W. Rülling, and C. Storb.
On Continuous Homotopic One Layer Routing.
In ACM Geometry Conference 88, pages 392–402, 1988.
72: K. Mehlhorn and W. Rülling.
Compaction on the Torus.
IEEE Transactions on CAD of Integrated Circuits and Systems, 9(4):389–397, 1990.
71: K. Mehlhorn and C.-K. Yap.
Constructive Whitney-Graustein Theorem: Or how to Untangle Closed Planar Curves.
SIAM Journal of Computing, 20(4):603–621, 1991.
70: R. K. Ahuja, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan.
Faster algorithms for the shortest path problem.
Journal of the ACM, 3(2):213–223, 1990.
69: K. Mehlhorn.
A Faster Approximation Algorithm for the Steiner Problem in Graphs.
Information Processing Letters, 27(2):125–128, 1988.
68: K. Mehlhorn and S. Näher.
Compaction with automatic jog insertion.
IEEE Transactions on CAD of Integrated Circuits and Systems, 9(2):158–166, 1990.
67: H. Alt, K. Mehlhorn, H. Wagener, and E. Welzl.
Congruence, Similarity, and Symmetries of Geometric Objects.
Journal of Discrete and Computational Geometry, 3:237–256, 1988.
66: H. Alt, T. Hagerup, K. Mehlhorn, and F. Preparata.
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones.
SIAM Journal of Computing, 16(4):808–835, 1987.
65: K. Mehlhorn and F. Preparata.
$AT^{2}$ -Optimal Integer Division with Computation Time $\Omega$ (log $n^{1+\epsilon}$ ).
Information and Computation, 72:270–282, 1987.
64: K. Mehlhorn, S. Näher, and H. Alt.
A Lower Bound on the Complexity of the Union-Split-Find Problem.
SIAM Journal of Computing, 17(6):1093–1102, 1988.
63: O. Fries, K. Mehlhorn, S. Näher, and A. Tsakalidis.
A $\hbox{\ log\ log\ }n$ Data Structure for Three-Sided Range Queries.
Information Processing Letters, 25(4):269–273, 1987.
62: T. Lengauer and K. Mehlhorn.
VLSI Complexity, Efficient VLSI Algorithms and the HILL Design System.
In C. Trullemans, editor, Algorithmics in VLSI, International Lecture Series in Computer Science, pages 33–89, 1987.
61: H. Jung and K. Mehlhorn.
Parallel Algorithms for Computing Maximal Independent Sets in Trees and for Updating Minimum Spanning Trees.
Information Processing Letters, 27(5):227–236, 1988.
60: K. Mehlhorn and B.H. Schmidt.
On BF-Orderable Graphs.
Discrete Applied Mathematics, 15:315–327, 1986.
59: K. Mehlhorn.
Über Verdrahtungsalgorithmen.
Informatik-Spektrum, 9:227–234, 1986.
58: M. Fürer and K. Mehlhorn.
$AT^{2}$ -Optimal Galois Field Multiplier for VLSI.
IEEE Transactions on Computers, 38(9):1333–1336, 1989.
57: K. Hoffmann, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan.
Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees.
Information & Control, 68(1–3):170–184, 1986.
56: K. Mehlhorn, F.P. Preparata, and M. Sarrafzadeh.
Channel Routing in Knock-Knee Mode: Simplified Algorithms and Proofs.
Algorithmica, 1:213–221, 1986.
55: K. Mehlhorn and A. Tsakalidis.
An Amortized Analysis of Insertions into AVL-Trees.
SIAM Journal of Computing, 15(1):22–33, 1986.
54: M. Kaufmann and K. Mehlhorn.
Routing through a Generalized Switchbox.
Journal of Algorithms, 7:510–531, 1986.
53: M. Becker and K. Mehlhorn.
Algorithms for Routing in Planar Graphs.
Acta Informatica, 23:163–176, 1986.
52: K. Mehlhorn and S. Näher.
Dynamic fractional cascading.
Algorithmica, 5(2):215–241, 1990.
51: K. Mehlhorn and F.P. Preparata.
Routing Through a Rectangle.
Journal of the ACM, 33(1):60–85, 1986.
50: S. Hertel and K. Mehlhorn.
Fast Triangulation of the Plane with Respect to Simple Polygons.
Information & Control, 64(1–3), 1985.
49: K. Mehlhorn and A. Tsakalidis.
Dynamic Interpolation Search.
In Proceedings of the 12th International Conference on Automata, Languages and Programming (ICALP'85), volume 194 of Lecture Notes in Computer Science, pages 424–434. Springer, 1985.
48: K. Mehlhorn and K. Simon.
Intersecting Two Polyhedra One of which is Convex.
In Proceedings of Fundamentals of Computation Theory (FCT'85), volume 199 of Lecture Notes in Computer Science, pages 534–542. Springer, 1985.
47: O. Fries, K. Mehlhorn, and S. Näher.
Dynamization of Geometric Data Structures.
In Proceedings of the ACM Conference on Computational Geometry, pages 168–176, 1985.
46: H. Alt and K. Mehlhorn.
Searching Semi-sorted Tables.
SIAM Journal of Computing, 14(4):840–848, 1985.
45: H. Mannila and K. Mehlhorn.
A Fast Algorithm for Renaming a Set of Clauses as a Horn Set.
Information Processing Letters, 21(5):269–272, 1985.
44: K. Mehlhorn.
$AT^{2}$ Optimal VLSI integer division and integer square rooting.
Integration, the VLSI Journal, 2:164–167, 1984.
43: T. Lengauer and K. Mehlhorn.
The HILL System: A Design Environment for the Hierarchical Spezification, Compaction, and Simulation of Integrated Circuit Layouts.
In Paul Penfield Ir., editor, Proceedings of the MIT VLSI Conference, pages 139–149. Artech House, Inc., 1984.
42: S. Hertel, M. Mäntylä, K. Mehlhorn, and J. Nievergelt.
Space Sweep Solves Intersection of Convex Polyhedra.
Acta Informatica, 21:501–519, 1984.
41: H. Alt, K. Mehlhorn, and J. Munro.
Partial Match Retrieval in Implicit Data Structures.
Information Processing Letters, 19(2):61–65, 1984.
40: K. Mehlhorn and U. Vishkin.
Randomized and Deterministic Simulations of PRAMs by Parallel Machines with Restricted Granularity of Parallel Memories.
Acta Informatica, 21:339–374, 1984.
39: K. Mehlhorn and F.P. Preparata.
$AT^{2}$ -Optimal VLSI Multipliers with Minimum Computation Time.
Information & Control, 58:137–156, 1983.
38: B.v. Braunmühl, S. Cook, K. Mehlhorn, and R. Verbeek.
The Recognition of Deterministic CFLs in Small Time and Space.
Information & Control, 56:34–51, 1983.
37: K. Mehlhorn and B.H. Schmidt.
A Single Source Shortest Path Algorithm for Graphs with Separators.
In Proceedings of the Fundamentals of Computation Theory (FCT'83), volume 158 of Lecture Notes in Computer Science, pages 302–309. Springer, 1983.
36: J.-W. Hong, K. Mehlhorn, and A. Rosenberg.
Cost Tradeoffs in Graph Embeddings with Applications.
Journal of the ACM, 30(4):709–728, 1983.
35: B. Eisenbarth, N. Ziviani, G.H. Gonnet, K. Mehlhorn, and D. Wood.
The Theory of Fringe Analysis and its Application to Trees and -Trees.
Information & Control, 55:125–174, 1982.
34: M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninnke, W. Keber, K. Mehlhorn, S. Näher, H. Rohnert, and T. Winter.
A Probabilistic Algorithm for Vertex Connectivity of Graphs.
Information Processing Letters, 15(3):135–136, 1982.
33: K. Mehlhorn.
On the Program Size of Perfect and Universal Hash Functions.
In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (FOCS'82), pages 170–175, 1982.
32: K. Mehlhorn and E.M. Schmidt.
Las Vegas is Better than Determinism in VLSI and Distributed Computing.
In Proceedings of the 14th Annual ACM SIGACT Symposiumon Theory of Computing (STOC'82), 1982.
31: S. Huddlestone and K. Mehlhorn.
A new data structure for representing sorted lists.
Acta Informatica, 17(2):157–184, 1982.
30: K. Mehlhorn.
A Partial Analysis of Height-balanced Trees under Random Insertions and Deletions.
SIAM Journal of Computing, 11(4):748–760, 1982.
29: T. Lengauer and K. Mehlhorn.
Four Results On the Complexity of VLSI Computation.
Advances in Computing Research, 2:1–22, 1984.
28: S. Huddleston and K. Mehlhorn.
Robust Balancing in -trees.
In Proceedings of the 5th GI-Conference on Theoretical Computer Science, volume 104 of Lecture Notes in Computer Science, pages 234–244. Springer, 1981.
27: K. Mehlhorn and M. Overmars.
Optimal Dynamization of Decomposable Searching Problems.
Information Processing Letters, 12(2):93–98, 1981.
26: K. Mehlhorn.
A Lower Bound on the Efficiency of Static to Dynamic Transforms of Data Structures.
Math. Systems Theory, 15:1–16, 1981.
25: K. Mehlhorn.
Arbitrary Weight Changes in Dynamic Trees.
RAIRO Theor. Inform., 15(3):183–211, 1981.
24: K. Mehlhorn.
An Efficient Algorithm for the Construction of Nearly Optimal Prefix Codes.
IEEE Transaction on Information Theory, IT-26(5):513–517, 1980.
23: R. Güttler, K. Mehlhorn, and W. Schneider.
Binary Search Trees: Average and Worst Case Behaviour.
EIK, 1–3:42–61, 1980.
22: N. Blum and K. Mehlhorn.
On the Average Number of Rebalancing Steps in Weight-Balanced Trees.
Theoretical Computer Science, 11:303–320, 1980.
21: D. Altenkamp and K. Mehlhorn.
Codes: Unequal Letter Costs, Unequal Probabilities.
Journal of the ACM, 27(3):412–427, 1980.
20: K. Mehlhorn.
Aspekte der Komplexitätstheorie illustriert am Beispiel des Sortierens.
In Proceedings of the GI-Jahrestagung 1979, volume 19 of Informatik-Fachberichte, pages 16–23, 1979.
19: K. Mehlhorn.
Searching, Sorting, and Information Theory.
In Proceedings of the Mathematical Foundations of Computer Science (MFCS'79), volume 74 of Lecture Notes in Computer Science, pages 67–78. Springer, 1979.
18: K. Mehlhorn.
Sorting Presorted Files.
In Proceedings of the 4th GI-Conference on Theoretical Computer Science, volume 67 of Lecture Notes in Computer Science, pages 199–212. Springer, 1979.
17: K. Mehlhorn.
Dynamic Data Structures.
Mathematical Centre Tracts, 108:71–96, 1979.
16: K. Mehlhorn.
Dynamic Binary Search.
SIAM Journal of Computing, 8(2):175–198, 1979.
15: K. Mehlhorn.
Some Remarks on Boolean Sums.
Acta Informatica, 12:371–375, 1979.
14: K. Mehlhorn.
Parsing Marco-Grammars Top-Down.
Information & Control, 40(2):123–143, 1979.
13: H. Alt and K. Mehlhorn.
Complexity Arguments in Algebraic Language Theory.
RAIRO Theor. Inform., 13(3):217–225, 1979.
12: K. Mehlhorn and M. Tsagarakis.
On the Isomorphism of two Algorithms: Hu/Tucker and Garsia/Wachs.
In Colloque de Lille `Les Arbres en Algebre et en Programmation', 1979.
11: K. Mehlhorn.
Effiziente Algorithmen: Ein Beispiel.
Informatik-Spektrum, 1:81–89, 1978.
10: K. Mehlhorn.
A Best Possible Bounds for the Weighted Path Length of Binary Search Trees.
SIAM Journal of Computing, 6(2):235–239, 1977.
9: P. Deussen and K. Mehlhorn.
Van Wijngarden Grammars and Space Complexity Class EXSPACE.
Acta Informatica, 8(2):193–199, 1977.
8: K. Mehlhorn.
An Improved Lower Bound on the Formula Complexity of Context-Free Recognition.
EIK, 12(11/12):523–524, 1976.
7: K. Mehlhorn.
Polynomial and Abstract Subrecursive Classes.
Journal of Computer and System Sciences, 12:147–178, 1976.
6: K. Mehlhorn and Z. Galil.
Monotone Switching Circuits and Boolean Matrix Product.
Computing, 16:99–111, 1976.
5: K. Mehlhorn.
Bracket Languages are Recognizable in Logarithmic Space.
Information Processing Letters, 5(6):168–170, 1976.
4: H. Alt and K. Mehlhorn.
Lower Bounds on the Space Complexity of Context-Free Recognition.
In Proceedings of the 3rd International Colloquium on Automata, Languages and Progr amming (ICALP'76), pages 338–354. Edinburgh University Press, 1976.
3: K. Mehlhorn.
Nearly Optimal Binary Search Trees.
Acta Informatica, 5:287–295, 1975.
2: K. Mehlhorn.
The `Almost All' Theory of Subrecursive Degrees is Decidable.
In Proceedings of the 2nd International Colloquium of Automata, Languages and Programming (ICALP'74), volume 14 of Lecture Notes in Computer Science, pages 317–325. Springer, 1974.
1: K. Mehlhorn.
On the Size of Sets of Computable Functions.
In Proceedings of the 14th IEEE Symposium on Automata and Switching Theory, pages 190–196, 1973.