Vi inför en ny metod för att beräkna ett ungefärligt maximalt s-t-flöde i en kapacierad, oriktad graf. Detta flöde beräknas genom att lösa en sekvens av elektriska flödesproblem. Varje elektriskt flöde ges av lösningen av ett system av linjära ekvationer i en Laplacian matris, och därmed kan ungefär beräknas i nästan linjär tid. Med detta tillvägagångssätt utvecklar vi den snabbaste kända algoritmen för att beräkna ungefär maximalt S-t flöden. För en graf med n hörn och m kanter beräknar vår algoritm a (1 − )-ungefär maximal s-t flöde i tid 1 e O(mn 1/3 −11/3 ). En dubbel version av vårt tillvägagångssätt ger den snabbaste kända algoritmen för att beräkna en (1+ ) - ungefär minsta s-t snitt. Det tar e O(m + n 4/3 −16/3 ) tid. Tidigare har det bästa beroendet av m och n uppnåtts genom algoritmen Goldberg och Rao (J. ACM 1998), som kan användas för att beräkna ungefär maximal s-t flöden i tiden e O(m ε n −1 ), och ungefär minsta s-t nedskärningar i tiden e O(m + n 3/2 −3 ).
År 2010, Christiano m.fl. REF beskrev ett nytt linjärt algebraiskt tillvägagångssätt för problemet som fann ε-ungefär maximala s-t-flöden i tiden O(mn 1/3 poly(1/ε)).
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}