David Eppstein – Publications

Publications with Amir Nayyeri

• 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.