Dokładnie płaski przepływ elektryczny

Rozważmy sieć elektryczną zamodelowaną jako płaski wykres G, gdzie każda krawędź reprezentuje rezystor 1 Ω. Jak szybko możemy obliczyć dokładną efektywną rezystancję między dwoma wierzchołkami w G? Równolegle, jak szybko możemy obliczyć dokładny prąd płynący wzdłuż każdej krawędzi, jeśli podłączymy baterię 1 V do dwóch wierzchołków w G?

Znane prawa Kirchhoffa dotyczące napięcia i prądu redukują ten problem do rozwiązania układu równań liniowych z jedną zmienną na krawędź. Nowsze wyniki - opisane wyraźnie przez Kleina i Randicia (1993), ale dorozumiane we wcześniejszej pracy Doyle'a i Snella (1984) - zmniejszają problem do rozwiązania układu liniowego z jedną zmienną na wierzchołek, reprezentującą potencjał tego węzła ; macierzą tego układu liniowego jest macierz Laplaciana na wykresie.

Każdy układ liniowy można rozwiązać dokładnie w czasie za pomocą zagnieżdżonego podziału i płaskich separatorów [ Lipton Rose Tarjan 1979 ]. Czy to najszybszy znany algorytm?$O(n^{3/2})$

Ostatnie przełomowe wyniki Spielmana, Tenga i innych sugerują, że system Laplaciana na dowolnych wykresach można rozwiązać w przybliżeniu w czasie prawie liniowym. Zobacz [ Koutis Miller Peng 2010 ], aby zobaczyć aktualny najlepszy czas trwania, oraz ten niesamowity artykuł Erici Klarreich z Simons Foundation, aby uzyskać ogólny przegląd. Ale szczególnie interesują mnie dokładne algorytmy dla grafów płaskich .

Załóżmy, że model obliczeniowy obsługuje dokładną rzeczywistą arytmetykę w stałym czasie.

$O(\sqrt{n^\omega})$

$O(\sqrt{n^\omega})$