Kurt Mehlhorn

From MaRDI portal
Person:270030

Available identifiers

zbMath Open mehlhorn.kurtWikidataQ90313 ScholiaQ90313MaRDI QIDQ270030

List of research outcomes

PublicationDate of PublicationType
On the all-pairs shortest path algorithm of Moffat and Takaoka2023-05-08Paper
A complete and efficient algorithm for the intersection of a general and a convex polyhedron2023-01-18Paper
Four results on randomized incremental constructions2022-08-18Paper
Fair Division of Indivisible Goods for a Class of Concave Valuations2022-08-02Paper
On fair division for indivisible items2022-07-21Paper
https://portal.mardi4nfdi.de/entity/Q50909622022-07-21Paper
Multi-Finger Binary Search Trees2022-07-21Paper
Trustworthy Graph Algorithms (Invited Talk)2022-07-21Paper
Physarum-inspired multi-commodity flow dynamics2022-05-17Paper
The maximum-level vertex in an arrangement of lines2022-03-21Paper
A Little Charity Guarantees Almost Envy-Freeness2021-09-10Paper
A Little Charity Guarantees Almost Envy-Freeness2021-02-02Paper
Convergence of the non-uniform directed physarum model2020-03-20Paper
Convergence of the non-uniform physarum dynamics2020-03-20Paper
Ratio-balanced maximum flows2019-09-20Paper
The Cost of Address Translation2019-09-12Paper
Sequential and Parallel Algorithms and Data Structures2019-09-05Paper
Two results on slime mold computations2019-05-21Paper
\textit{Physarum} can compute shortest paths2019-05-14Paper
https://portal.mardi4nfdi.de/entity/Q57433942019-05-10Paper
The query complexity of a permutation-based variant of mastermind2019-05-03Paper
Maintaining discrete probability distributions optimally2019-03-29Paper
AT/sup 2/-optimal Galois field multiplier for VLSI2018-09-14Paper
On testing substitutability2018-07-17Paper
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market2018-07-16Paper
https://portal.mardi4nfdi.de/entity/Q46080452018-03-15Paper
https://portal.mardi4nfdi.de/entity/Q46062772018-03-02Paper
A Note On Spectral Clustering2018-03-02Paper
Earning limits in Fisher markets with spending-constraint utilities2018-02-13Paper
Corrigendum to: ``Faster algorithms for computing Hong's bound on absolute positiveness2018-01-12Paper
Look — a Lazy Object-Oriented Kernel for geometric computation2017-09-29Paper
Certifying 3-edge-connectivity2017-03-03Paper
Fair Matchings and Related Problems2017-02-21Paper
From approximate factorization to root isolation2017-02-10Paper
Towards more practical linear programming-based techniques for algorithmic mechanism design2017-02-01Paper
A still simpler way of introducing interior-point method for linear programming2016-12-14Paper
Opposition Frameworks2016-11-30Paper
On a Model of Virtual Address Translation2016-10-24Paper
An analysis of the highest-level selection rule in the preflow-push max-flow algorithm2016-06-16Paper
Improved balanced flow computation using parametric flow2016-05-18Paper
Fair matchings and related problems2016-04-06Paper
On the Implementation of Combinatorial Algorithms for the Linear Exchange Market2016-01-27Paper
Self-Adjusting Binary Search Trees: What Makes Them Tick?2015-11-19Paper
Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design2015-11-04Paper
Greedy Is an Almost Optimal Deque2015-10-30Paper
On randomized fictitious play for approximating saddle points over convex sets2015-10-19Paper
Rank-maximal matchings2015-09-02Paper
Strongly stable matchings in time O ( nm ) and extension to the hospitals-residents problem2015-09-02Paper
Computing real roots of real polynomials2015-08-24Paper
https://portal.mardi4nfdi.de/entity/Q55018162015-08-14Paper
https://portal.mardi4nfdi.de/entity/Q55018502015-08-14Paper
https://portal.mardi4nfdi.de/entity/Q55012442015-08-03Paper
https://portal.mardi4nfdi.de/entity/Q55013552015-08-03Paper
Pattern-avoiding access in binary search trees2015-07-24Paper
A framework for the verification of certifying computations2015-06-23Paper
A combinatorial polynomial algorithm for the linear Arrow-Debreu market2015-06-09Paper
Minimum cycle bases2014-11-18Paper
Certifying algorithms2014-10-24Paper
https://portal.mardi4nfdi.de/entity/Q29216972014-10-13Paper
https://portal.mardi4nfdi.de/entity/Q29217272014-10-13Paper
https://portal.mardi4nfdi.de/entity/Q29217762014-10-13Paper
Cycle bases in graphs characterization, algorithms, complexity, and applications2014-10-07Paper
Additive spanners and (α, β)-spanners2014-09-09Paper
New Approximability Results for the Robust k-Median Problem2014-09-02Paper
From approximate factorization to root isolation with application to cylindrical algebraic decomposition2014-07-16Paper
Improving the price of anarchy for selfish routing via coordination mechanisms2014-07-03Paper
https://portal.mardi4nfdi.de/entity/Q53966942014-02-03Paper
Certifying 3-edge-connectivity2013-12-06Paper
The Query Complexity of Finding a Hidden Permutation2013-09-13Paper
Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds2013-08-07Paper
A combinatorial polynomial algorithm for the linear Arrow-Debreu market2013-08-06Paper
On randomized fictitious play for approximating saddle points over convex sets2013-06-11Paper
Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge2013-03-07Paper
Online graph exploration: New results on old and new algorithms2013-01-07Paper
Counting Arbitrary Subgraphs in Data Streams2012-11-01Paper
Isolating real roots of real polynomials2012-05-13Paper
An \(O(n+m)\) certifying triconnnectivity algorithm for Hamiltonian graphs2012-04-26Paper
A general approach to the analysis of controlled perturbation algorithms2011-12-28Paper
Improving the price of anarchy for selfish routing via coordination mechanisms2011-09-16Paper
Approximate Counting of Cycles in Streams2011-09-16Paper
Online Graph Exploration: New Results on Old and New Algorithms2011-07-07Paper
Reliable Geometric Computing2011-04-07Paper
New approximation algorithms for minimum cycle bases of graphs2011-03-30Paper
Arrangements on parametric surfaces. I: General framework and infrastructure2011-02-19Paper
A deterministic algorithm for isolating real roots of a real polynomial2010-11-19Paper
Assigning papers to referees2010-10-07Paper
Reliable and Efficient Geometric Computing2010-09-14Paper
Progress on Certifying Algorithms2010-09-07Paper
Algorithmen und Datenstrukturen2010-07-19Paper
Faster algorithms for computing Hong's bound on absolute positiveness2010-05-21Paper
Algorithms - ESA 20032010-03-03Paper
Breaking the O(m 2 n) Barrier for Minimum Cycle Bases2009-10-29Paper
Cycle bases of graphs and sampled manifolds2009-10-16Paper
Faster Algorithms for Minimum Cycle Basis in Directed Graphs2009-08-20Paper
Note on the paper ``K-vertex guarding simple polygons2009-07-27Paper
A separation bound for real algebraic expressions2009-07-24Paper
https://portal.mardi4nfdi.de/entity/Q53210742009-07-22Paper
An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs2009-03-24Paper
Optimal search for rationals2009-03-23Paper
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs2009-03-12Paper
Reliable and Efficient Computational Geometry Via Controlled Perturbation2009-03-12Paper
Matchings in Graphs Variations of the Problem2009-03-03Paper
Reply to “Backward Error Analysis ...”2009-01-27Paper
Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step2008-09-25Paper
Minimum Cycle Bases in Graphs Algorithms and Applications2008-09-17Paper
Popular Matchings2008-08-14Paper
https://portal.mardi4nfdi.de/entity/Q35077722008-06-20Paper
Algorithms and Data Structures2008-05-28Paper
Classroom examples of robustness problems in geometric computations2008-03-26Paper
Reliable and Efficient Geometric Computing2008-03-11Paper
Mathematical Foundations of Computer Science 20032007-12-07Paper
New bounds for the Descartes method2007-10-23Paper
STACS 20042007-10-01Paper
STACS 20042007-10-01Paper
New Approximation Algorithms for Minimum Cycle Bases of Graphs2007-09-03Paper
Algorithms to compute minimum cycle basis in directed graphs2007-08-23Paper
Boolean operations on 3D selective Nef complexes: data structure, algorithms, optimized implementation and experiments2007-07-04Paper
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs2007-05-03Paper
Reliable and Efficient Geometric Computing2007-05-02Paper
Algorithms and Computation2006-11-14Paper
Graph Drawing2006-11-13Paper
Matching algorithms are fast in sparse random graphs2006-10-25Paper
Computer Algebra in Scientific Computing2006-07-07Paper
Algorithms – ESA 20052006-06-27Paper
POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA2006-05-29Paper
Maximum network flow with floating point arithmetic.2006-01-17Paper
Automata, Languages and Programming2006-01-10Paper
Algorithms and Computation2005-12-22Paper
Algorithms and Computation2005-12-22Paper
STACS 20052005-12-02Paper
Experimental and Efficient Algorithms2005-11-30Paper
Automata, Languages and Programming2005-08-24Paper
Algorithms – ESA 20042005-08-18Paper
Structural filtering: a paradigm for efficient and exact geometric programs2005-08-05Paper
Implementation of O ( nm log n ) weighted matchings in general graphs2005-08-04Paper
FURTHEST SITE ABSTRACT VORONOI DIAGRAMS2005-06-10Paper
RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS2005-06-10Paper
Infimaximal Frames: A Technique for Making Lines Look Like Segments2004-09-29Paper
https://portal.mardi4nfdi.de/entity/Q44730342004-08-04Paper
https://portal.mardi4nfdi.de/entity/Q44712902004-07-28Paper
https://portal.mardi4nfdi.de/entity/Q44713062004-07-28Paper
An efficient graph algorithm for dominance constraints2004-03-14Paper
https://portal.mardi4nfdi.de/entity/Q44263582003-09-16Paper
A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms2003-08-19Paper
https://portal.mardi4nfdi.de/entity/Q44138012003-07-21Paper
https://portal.mardi4nfdi.de/entity/Q44113472003-07-08Paper
https://portal.mardi4nfdi.de/entity/Q44113572003-07-08Paper
https://portal.mardi4nfdi.de/entity/Q44114042003-07-08Paper
Scanning multiple sequences via cache memory2003-06-02Paper
https://portal.mardi4nfdi.de/entity/Q48011772003-04-07Paper
https://portal.mardi4nfdi.de/entity/Q47967072003-04-03Paper
https://portal.mardi4nfdi.de/entity/Q47961792003-03-02Paper
A polyhedral approach to sequence alignment problems2002-11-13Paper
A correctness certificate for the Stoer-Wagner min-cut algorithm2002-07-25Paper
LOOK: A lazy object-oriented kernel design for geometric computation2002-06-24Paper
https://portal.mardi4nfdi.de/entity/Q27683862002-03-24Paper
https://portal.mardi4nfdi.de/entity/Q27539492001-12-18Paper
https://portal.mardi4nfdi.de/entity/Q27541772001-12-09Paper
https://portal.mardi4nfdi.de/entity/Q27384892001-11-05Paper
https://portal.mardi4nfdi.de/entity/Q27291032001-10-23Paper
Traveling Salesman-Based Curve Reconstruction in Polynomial Time2001-06-21Paper
A strong and easily computable separation bound for arithmetic expressions involving radicals2001-01-29Paper
https://portal.mardi4nfdi.de/entity/Q49433522000-12-12Paper
A lower bound for area-universal graphs2000-08-02Paper
Curve reconstruction: Connecting dots with good reason2000-07-27Paper
https://portal.mardi4nfdi.de/entity/Q49455372000-06-07Paper
https://portal.mardi4nfdi.de/entity/Q49526862000-05-10Paper
On the Expected Depth of Random Circuits2000-03-07Paper
https://portal.mardi4nfdi.de/entity/Q47021881999-11-24Paper
https://portal.mardi4nfdi.de/entity/Q42684601999-10-31Paper
https://portal.mardi4nfdi.de/entity/Q42524001999-06-17Paper
https://portal.mardi4nfdi.de/entity/Q42181501999-05-10Paper
Checking geometric programs or verification of geometric structures1999-05-03Paper
https://portal.mardi4nfdi.de/entity/Q43855111998-05-04Paper
Maintaining dynamic sequences under equality tests in polylogarithmic time1997-06-30Paper
An $o(n^3 )$-Time Maximum-Flow Algorithm1997-06-09Paper
https://portal.mardi4nfdi.de/entity/Q43351891997-04-23Paper
https://portal.mardi4nfdi.de/entity/Q43352121997-04-23Paper
https://portal.mardi4nfdi.de/entity/Q47182231997-04-10Paper
https://portal.mardi4nfdi.de/entity/Q31229141997-03-05Paper
A method for obtaining randomized algorithms with small tail probabilities1997-03-03Paper
Algorithms for dense graphs and networks on the random access computer1996-10-21Paper
On the embedding phase of the Hopcroft and Tarjan planarity testing algorithm1996-10-20Paper
Lower bounds for set intersection queries1995-10-09Paper
Dynamic Point Location in General Subdivisions1995-09-26Paper
A communication-randomness tradeoff for two-processor systems1995-05-28Paper
https://portal.mardi4nfdi.de/entity/Q47633931995-04-11Paper
https://portal.mardi4nfdi.de/entity/Q47634121995-04-11Paper
On local routing of two-terminal nets1995-02-07Paper
https://portal.mardi4nfdi.de/entity/Q42815331994-11-13Paper
Randomized incremental construction of abstract Voronoi diagrams1994-10-19Paper
Dynamic Perfect Hashing: Upper and Lower Bounds1994-10-17Paper
A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs1994-05-10Paper
https://portal.mardi4nfdi.de/entity/Q31404211993-12-15Paper
Dynamic interpolation search1993-12-06Paper
Four results on randomized incremental constructions1993-11-01Paper
Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection1993-11-01Paper
https://portal.mardi4nfdi.de/entity/Q42019331993-09-06Paper
https://portal.mardi4nfdi.de/entity/Q40398491993-06-05Paper
https://portal.mardi4nfdi.de/entity/Q40386951993-05-18Paper
\(k\) versus \(k+1\) index registers and modifiable versus non-modifiable programs1993-01-17Paper
Simultaneous inner and outer approximation of shapes1993-01-17Paper
Approximate motion planning and the complexity of the boundary of the union of simple geometric figures1993-01-17Paper
A lower bound for the nondeterministic space complexity of context-free recognition1993-01-16Paper
https://portal.mardi4nfdi.de/entity/Q39759331992-06-26Paper
Constructive Whitney–Graustein Theorem: Or How to Untangle Closed Planar Curves1992-06-25Paper
On the construction of abstract Voronoi diagrams1991-01-01Paper
Dynamic fractional cascading1990-01-01Paper
Hidden line elimination for isooriented rectangles1990-01-01Paper
Bounded ordered dictionaries in O(log log N) time and O(n) space1990-01-01Paper
Dynamic deferred data structuring1990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32101991990-01-01Paper
Faster algorithms for the shortest path problem1990-01-01Paper
https://portal.mardi4nfdi.de/entity/Q47321191989-01-01Paper
Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees1988-01-01Paper
Congruence, similarity, and symmetries of geometric objects1988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37967881988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38041891988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38098141988-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38133391988-01-01Paper
A Lower Bound on the Complexity of the Union-Split-Find Problem1988-01-01Paper
A faster approximation algorithm for the Steiner problem in graphs1988-01-01Paper
Area-time optimal division for \(T=\Omega ((\log \,n)^{1+\epsilon})\)1987-01-01Paper
A log log n data structure for three-sided range queries1987-01-01Paper
Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones1987-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37749431987-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37774751987-01-01Paper
On BF-orderable graphs1986-01-01Paper
Channel routing in knock-knee mode: Simplified algorithms and proofs1986-01-01Paper
An Amortized Analysis of Insertions into AVL-Trees1986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37273811986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37300201986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37350461986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37477401986-01-01Paper
Routing through a generalized switchbox1986-01-01Paper
Sorting jordan sequences in linear time using level-linked search trees1986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q47274341986-01-01Paper
https://portal.mardi4nfdi.de/entity/Q36860501985-01-01Paper
Fast triangulation of the plane with respect to simple polygons1985-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37008331985-01-01Paper
Searching Semisorted Tables1985-01-01Paper
https://portal.mardi4nfdi.de/entity/Q37079231985-01-01Paper
Space sweep solves intersection of convex polyhedra1984-01-01Paper
Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories1984-01-01Paper
Partial match retrieval in implicit data structures1984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32197511984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32197521984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32197531984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q32197641984-01-01Paper
https://portal.mardi4nfdi.de/entity/Q36987081984-01-01Paper
The recognition of deterministic CFLs in small time and space1983-01-01Paper
Area—Time optimal VLSI integer multiplier with minimum computation time1983-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33401511983-01-01Paper
https://portal.mardi4nfdi.de/entity/Q36705551983-01-01Paper
https://portal.mardi4nfdi.de/entity/Q36705581983-01-01Paper
Cost Trade-offs in Graph Embeddings, with Applications1983-01-01Paper
A new data structure for representing sorted lists1982-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33214721982-01-01Paper
A Partial Analysis of Height-Balanced Trees under Random Insertions and Deletions1982-01-01Paper
The theory of fringe analysis and its application to 23 trees and b-trees1982-01-01Paper
Optimal dynamization of decomposable searching problems1981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q33439211981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39025011981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39071001981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39175011981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39206241981-01-01Paper
Lower bounds on the efficiency of transforming static data structures into dynamic structures1981-01-01Paper
https://portal.mardi4nfdi.de/entity/Q39531701981-01-01Paper
On the average number of rebalancing operations in weight-balanced trees1980-01-01Paper
An efficient algorithm for constructing nearly optimal prefix codes1980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38835201980-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38901121980-01-01Paper
Codes: Unequal Probabilities, Unequal Letter Cost1980-01-01Paper
Some remarks on Boolean sums1979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q38546271979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41785011979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41825321979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41959581979-01-01Paper
Dynamic Binary Search1979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41959601979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41963541979-01-01Paper
Parsing macro grammars top down1979-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41995231979-01-01Paper
Effiziente Algorithmen: Ein Beispiel1978-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41626741978-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41652851978-01-01Paper
Van Wijngaarden grammars and space complexity class EXSPACE1977-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41257661977-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41331221977-01-01Paper
A Best Possible Bound for The Weighted Path Length of Binary Search Trees1977-01-01Paper
Monotone switching circuits and Boolean matrix product1976-01-01Paper
Polynomial and abstract subrecursive classes1976-01-01Paper
Bracket-languages are recognizable in logarithmic space1976-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41213941976-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41273991976-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41349751976-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41448081976-01-01Paper
Nearly optimal binary search trees1975-01-01Paper
https://portal.mardi4nfdi.de/entity/Q40728361975-01-01Paper
https://portal.mardi4nfdi.de/entity/Q40795181975-01-01Paper
https://portal.mardi4nfdi.de/entity/Q41381341974-01-01Paper
https://portal.mardi4nfdi.de/entity/Q47704821974-01-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Kurt Mehlhorn