Vi presenterar en nästan linjär tid algoritm som producerar högkvalitativa sparifierare av viktade grafer. Eftersom vi anger en viktad graf G = (V, E, w) och en parameter > 0, producerar vi en viktad delgraf H = (V, på, w) av G sådan att O(n log n/ 2 ) och för alla vektorer Detta förbättrar på sparifierarna konstruerade av Spielman och Teng, som hade O(n log c n) kanter för några stora konstant c, och på dem av Benczúr och Karger, som endast tillfredsställde (1) för x {0, 1} V. Vi konjecture förekomsten av sparsifierare med O (n) kanter, notera att dessa skulle generalisera begreppet expander grafer, som är konstant grad sparifierare för den fullständiga grafen. En viktig ingrediens i vår algoritm är en subrutin av oberoende intresse: en nästan linjär tidsalgoritm som bygger en datastruktur från vilken vi kan ifrågasätta det ungefärliga effektiva motståndet mellan två hörn i en graf i O(log n) tid.
Antalet kanter förbättrades senare till O(n log n/ 2 ) genom provtagning av varje kant med sannolikhet proportionell mot dess effektiva motstånd REF.
Graph sparsification by effective resistances
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}