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.
Spielman och Srivastava REF konstruerar bra sparifierare av viktade grafer via en effektiv algoritm för att beräkna approximativ effektiv resistens mellan två hörn, ett resultat som är ganska insiktsfullt på egen hand.
Graph sparsification by effective resistances
{'venue': "STOC '08", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}