David Eppstein - Publications
- All-pairs minimum cuts in near-linear time for surface-embedded graphs.
G. Borradaile,
D. Eppstein,
A. Nayyeri,
and C. Wulff-Nilsen.
arXiv:1411.7055.
Proc. 32nd Int. Symp. Computational Geometry, Boston, 2016.
Leibniz International Proceedings in Informatics (LIPIcs) 51, pp. 22:1–22:16.
We give the first known near-linear algorithms for constructing
Gomory–Hu trees of bounded-genus graphs, and we shave a log off
the time for the same problem on planar graphs.
- Low-stretch spanning trees of graphs with bounded width.
G. Borradaile,
E. Chambers,
D. Eppstein,
W. Maxwell, and
A. Nayyeri.
arXiv:2004.08375.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm
Theory (SWAT 2020).
Leibniz International
Proceedings in Informatics (LIPIcs) 162, 2020, pp. 15:1–15:19.
We describe a random distribution on the spanning trees of
bounded-bandwidth graphs such that each edge has bounded expected
stretch, along with several related results for other kinds of graph
widths.
Co-authors –
Publications –
David Eppstein –
Theory Group –
Inf. & Comp. Sci. –
UC Irvine
Semi-automatically filtered
from a common source file.