Thumbnail
Access Restriction
Open

Author Elkin, Michael ♦ Spielman, Daniel A. ♦ Emek, Yuval ♦ Teng, Shang-Hua
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Average Stretch ♦ Lower-stretch Spanning Tree ♦ Main Ingredient ♦ New Algorithm ♦ Input Graph ♦ Dominant Linear System ♦ Log Log ♦ Running Time ♦ Recent Solver ♦ Novel Graph Decomposition Technique ♦ Low-stretch Spanning Tree
Description We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch O(log 2 n log log n). Moreover, we show that this tree can be constructed in time O(m log n + n log 2 n) in general, and in time O(m log n) if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique. Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from m2 (O( √ log nlog log n)) to m log O(1) n, and to O(n log 2 n log log n) when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.
In STOC
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01