The Diameter of Randomly Perturbed Digraphs and Some Applications Export

@misc{citeulike:1300664, abstract = {The central observation of this paper is that if n random edges are added to any n-node connected graph or digraph then the resulting graph has diameter O(log n). We apply this to smoothed analysis of algorithms and property testing.}, author = {Flaxman, Abraham D. and Frieze, Alan M.}, citeulike-article-id = {1300664}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.8973}, keywords = {algorithm, analysis, diameter, digraphs, graphs, log, perturbed, randomly, smoothed, space}, posted-at = {2007-05-16 19:52:22}, priority = {0}, title = {The Diameter of Randomly Perturbed Digraphs and Some Applications}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.8973} }

TY - GEN ID - citeulike:1300664 L3 - citeulike-article-id:1300664 N2 - The central observation of this paper is that if n random edges are added to any n-node connected graph or digraph then the resulting graph has diameter O(log n). We apply this to smoothed analysis of algorithms and property testing. TI - The Diameter of Randomly Perturbed Digraphs and Some Applications KW - algorithm KW - analysis KW - diameter KW - digraphs KW - graphs KW - log KW - perturbed KW - randomly KW - smoothed KW - space AU - Flaxman, Abraham AU - Frieze, Alan UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.8973 ER -