68 citations · 76 across the 4 of their papers we have counts for
4 papers
Lower-Stretch Spanning Trees
Michael Elkin, Yuval Emek, Daniel A. Spielman +1
We prove that every weighted graph contains a spanning tree subgraph of average stretch O((log n log log n)^2). Moreover, we show how to construct such a tree in time O(m log^2 n).
Smoothed Analysis of Interior-Point Algorithms: Termination
Daniel A. Spielman, Shang-Hua Teng
We perform a smoothed analysis of the termination phase of an interior-point method. By combining this analysis with the smoothed analysis of Renegar's interior-point algorithm by…
Smoothed analysis of algorithms
Daniel A. Spielman, Shang-Hua Teng
Spielman and Teng introduced the smoothed analysis of algorithms to provide a framework in which one could explain the success in practice of algorithms and heuristics that could n…
Parallel Delaunay Refinement: Algorithms and Analyses
Dan A. Spielman, Shang-hua Teng, Alper Ungor
In this paper, we analyze the complexity of natural parallelizations of Delaunay refinement methods for mesh generation. The parallelizations employ a simple strategy: at each iter…