Med tanke på en oriktad graf G = (V, E) med kantkapaciteter ce ≥ 1 för E och en delmängd T av k hörn som kallas terminaler, säger vi att en graf H är en kvalitet-q skär glesare för G iff T (H), och för varje partition (A, B) av T, värdena för de minsta skärningar som separerar A och B i graferna G och H är inom en faktor q från varandra. Vi säger att H är en quality-q flow sparsifier för G iff T V (H), och för varje uppsättning D krav över terminalerna, värdena av den minsta egg trängsel till följd av fraktionerat routing kraven i D i diagram G och H är inom en faktor q från varandra. Hittills vertex sparifierare har studerats i en begränsad miljö där sparifieraren H inte är tillåten att innehålla några icke-terminala hörn, det vill säga V (H) = T. För denna inställning, effektiva algoritmer är kända för att konstruera kvalitet-O (logg k / log log k) skär och flöde vertex sparifierare, liksom en lägre gräns för  samt en lägre gräns för ε log k) på kvaliteten på alla flöden eller skär sparifierare. Vi studerar flöde och skär sparifierare i den mer allmänna inställningen där Steiner hörn är tillåtna, det vill säga, vi behöver inte längre att V (H) = T. Vi visar algoritmer för att konstruera konstant kvalitet skär sparifierare av storlek O(C 3 ) i tid poly(n) · 2 C, och konstant kvalitet flöde sparifierare av storlek C O (logglogg C) i tid n O(logg C) · 2 C, där C är den totala kapaciteten av kanterna incident på terminalerna.
Chuzhoy REF ger en konstant kvalitet skär och flöde sparifierar med storlek beroende på den totala kapaciteten av kanterna på terminalerna.
On vertex sparsifiers with Steiner nodes
{'venue': "STOC '12", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}