David Eppstein – Publications

Publications with William Maxwell

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

• On the treewidth of Hanoi graphs.
  D. Eppstein, D. Frishberg, and W. Maxwell.
  arXiv:2005.00179.
  Proc. 10th Int. Conf. Fun with Algorithms (FUN 2021).
  Leibniz International Proceedings in Informatics (LIPIcs) 157, 2020, pp. 13:1–13:21.
  Theor. Comput. Sci. 906: 1–17, 2022.

  The n-disc p-peg Hanoi graphs have treewidth within a polynomial factor of n^p − 1.