I. Abraham and O. Neiman, Using petal-decompositions to build a low stretch spanning tree, Proceedings of the 44th symposium on Theory of Computing, STOC '12, pp.395-406, 2012.
DOI : 10.1145/2213977.2214015

N. Alon, R. M. Karp, D. Peleg, and D. B. West, -Server Problem, SIAM Journal on Computing, vol.24, issue.1, pp.78-100, 1995.
DOI : 10.1137/S0097539792224474
URL : https://hal.archives-ouvertes.fr/halshs-00480214

J. D. Batson, D. A. Spielman, and N. Srivastava, Twice-Ramanujan Sparsifiers, SIAM Review, vol.56, issue.2, pp.315-334, 2014.
DOI : 10.1137/130949117
URL : http://arxiv.org/abs/0808.0163

J. D. Batson, D. A. Spielman, N. Srivastava, and S. Teng, Spectral sparsification of graphs, Communications of the ACM, vol.56, issue.8, pp.5687-94, 2013.
DOI : 10.1145/2492007.2492029

R. Beauwens, Lower eigenvalue bounds for pencils of matrices, Linear Algebra and its Applications, vol.85, p.101119, 1987.
DOI : 10.1016/0024-3795(87)90211-4

M. W. Bern, J. R. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo, Support-Graph Preconditioners, SIAM Journal on Matrix Analysis and Applications, vol.27, issue.4, pp.930-951, 2006.
DOI : 10.1137/S0895479801384019

E. Boman and B. Hendrickson, Support Theory for Preconditioning, SIAM Journal on Matrix Analysis and Applications, vol.25, issue.3, pp.694-717, 2003.
DOI : 10.1137/S0895479801390637

D. Chen and S. Toledo, Vaidya's preconditioners: implementation and experimental study, Elect. Trans. on Numerical Analysis, vol.16, pp.30-49, 2003.

M. B. Cohen, R. Kyng, G. L. Miller, J. Pachocki, R. Peng et al., Solving SDD linear systems in nearly mlog 1/2 n time, Proc. STOC, pp.343-352, 2014.

D. Hoske, D. Lukarski, H. Meyerhenke, and M. Wegner, Is Nearly-linear the Same in Theory and Practice? A Case Study with a Combinatorial Laplacian Solver, Proc. SEA, 2015.
DOI : 10.1007/978-3-319-20086-6_16

J. A. Kelner, L. Orecchia, A. Sidford, and Z. A. Zhu, A simple, combinatorial algorithm for solving SDD systems in nearly-linear time, Proceedings of the 45th annual ACM symposium on Symposium on theory of computing, STOC '13, pp.911-920, 2013.
DOI : 10.1145/2488608.2488724

A. Kolla, Y. Makarychev, A. Saberi, and S. Teng, Subgraph sparsification and nearly optimal ultrasparsifiers, Proceedings of the 42nd ACM symposium on Theory of computing, STOC '10, pp.57-66, 2010.
DOI : 10.1145/1806689.1806699
URL : http://arxiv.org/abs/0912.1623

Y. Koren, Drawing graphs by eigenvectors: theory and practice, Computers & Mathematics with Applications, vol.49, issue.11-12, 2005.
DOI : 10.1016/j.camwa.2004.08.015
URL : http://doi.org/10.1016/j.camwa.2004.08.015

I. Koutis, A. Levin, and R. Peng, Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices, ACM Transactions on Algorithms, vol.12, issue.2, 1209.
DOI : 10.1145/2743021

I. Koutis, G. L. Miller, and R. Peng, A fast solver for a class of linear systems, Communications of the ACM, vol.55, issue.10, pp.99-107, 2012.
DOI : 10.1145/2347736.2347759

D. Krishnan, R. Fattal, and R. Szeliski, Efficient preconditioning of laplacian matrices for computer graphics, ACM Transactions on Graphics, vol.32, issue.4, p.142, 2013.
DOI : 10.1145/2461912.2461992

Y. T. Lee and A. Sidford, Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp.147-156, 2013.
DOI : 10.1109/FOCS.2013.24

B. Levy and R. H. Zhang, Spectral geometry processing, ACM SIGGRAPH Course Notes, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00432422

Y. Nesterov, Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, SIAM Journal on Optimization, vol.22, issue.2, pp.341-362, 2012.
DOI : 10.1137/100802001

D. Poulalhon and G. Schaeffer, Optimal Coding and Sampling of Triangulations, Algorithmica, vol.46, issue.3-4, pp.505-527, 2006.
DOI : 10.1007/s00453-006-0114-8
URL : https://hal.archives-ouvertes.fr/hal-00159287

D. A. Spielman and S. Teng, Spectral Sparsification of Graphs, SIAM Journal on Computing, vol.40, issue.4, pp.981-1025, 2011.
DOI : 10.1137/08074489X

D. A. Spielman and S. Teng, A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning, SIAM Journal on Computing, vol.42, issue.1, pp.1-26, 2013.
DOI : 10.1137/080744888

D. A. Spielman and S. Teng, Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems, SIAM Journal on Matrix Analysis and Applications, vol.35, issue.3, pp.835-885, 2014.
DOI : 10.1137/090771430

D. A. Spielman and S. Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing , STOC '04, pp.81-90, 2004.
DOI : 10.1145/1007352.1007372

P. M. Vaidya, Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript, 1991.

N. K. Vishnoi, Lx = b. Foundations and Trends in Theoretical Computer Science, pp.1-141, 2013.