David Eppstein – Publications

A stronger lower bound on parametric minimum spanning trees.
D. Eppstein.
arXiv:2105.05371.
17th Algorithms and Data Structures Symp. (WADS 2021).
Springer, Lecture Notes in Comp. Sci. 12808 (2021), pp. 343–356, doi:10.1007/978-3-030-83508-8_25.
Algorithmica 85: 1738–1753, 2023 (special issue for WADS 2021), doi:10.1007/s00453-022-01024-9.

There exist graphs with edges labeled by linear real functions, such that the number of different minimum spanning trees obtained for different choices of the function argument is \(\Omega(m\log n)\). This improves an \(\Omega(m\alpha(n))\) lower bound from my previous paper "Geometric lower bounds for parametric matroid optimization".

(WADS'21 slides – Blog post: The constructive solid geometry of piecewise-linear functions)