Aliran listrik planar yang tepat

Pertimbangkan jaringan listrik yang dimodelkan sebagai grafik G planar, di mana setiap sisi mewakili resistor 1Ω. Seberapa cepat kita bisa menghitung resistensi efektif yang tepat antara dua simpul dalam G? Setara, seberapa cepat kita dapat menghitung arus yang tepat mengalir di sepanjang setiap tepi jika kita memasang baterai 1V ke dua simpul dalam G?

Undang-undang tegangan dan arus Kirchhoff yang terkenal mengurangi masalah ini untuk menyelesaikan sistem persamaan linear dengan satu variabel per edge. Hasil yang lebih baru - dijelaskan secara eksplisit oleh Klein dan Randić (1993) tetapi tersirat dalam karya sebelumnya Doyle dan Snell (1984) - mengurangi masalah untuk menyelesaikan sistem linear dengan satu variabel per simpul, mewakili potensi simpul itu ; matriks untuk sistem linier ini adalah matriks Laplacian dari grafik.

Entah sistem linear dapat diselesaikan tepat di waktu menggunakan diseksi bersarang dan pemisah planar [ Lipton Rose Tarjan 1979 ]. Apakah ini algoritma tercepat yang dikenal?$O(n^{3/2})$

Hasil mani terakhir dari Spielman, Teng, dan lainnya menyiratkan bahwa sistem Laplacian dalam grafik arbitrer dapat diselesaikan kira-kira dalam waktu dekat-linear. Lihat [ Koutis Miller Peng 2010 ] untuk waktu berjalan terbaik saat ini, dan artikel menakjubkan ini oleh Erica Klarreich di Yayasan Simons untuk ikhtisar tingkat tinggi. Tapi saya secara khusus tertarik pada algoritma yang tepat untuk grafik planar .

Asumsikan model perhitungan yang mendukung aritmatika nyata yang tepat dalam waktu yang konstan.

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

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