836 citations · 912 across the 5 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2004
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).
cs.DS2003★ 2 cited
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…