Analisis kompleksitas waktu untuk algoritma UST-CONN Reingold

Apa kompleksitas waktu yang tepat dari algoritma ruang log st-konektivitas yang tidak diarahkan oleh Omer Reingold?

cc.complexity-theory randomness Suresh Venkat
sumber

Harap lebih spesifik. Jelaskan pertanyaan Anda dengan cukup detail, dan kutip referensi yang sesuai.

MS Dousti

Saya pikir pertanyaannya cukup jelas: doi.acm.org/10.1145/1391289.1391291 adalah makalahnya.

András Salamon

Pertanyaannya cukup jelas bagi mereka yang bekerja di daerah tersebut, tetapi mungkin ide yang baik untuk meminta poster untuk memberikan informasi lebih banyak sehingga khalayak yang lebih luas dapat memahami pertanyaan tersebut.

Robin Kothari

Jawaban:

Tampaknya kompleksitas waktu dari algoritma Reingold tidak diperlakukan di kertas Reingold atau di buku teks Arora-Barak. Akan terlihat juga bahwa analisisnya agak membosankan, karena kompleksitas waktu tergantung pada grafik ekspander yang digunakan dalam konstruksi dan pada beberapa konstanta yang dipilih untuk "cukup besar".

$G$ $G'$ $l = O(\log n)$ $O$ $G'$ $d = 2^b$ $b$ $d^l = O(n^c)$ $c$ $c \ge 10^9b$

Janne H. Korhonen
sumber

lain kali, jangan tandai jawaban Anda sebagai komunitas wiki. Kalau tidak, Anda tidak akan mendapatkan kredit untuk jawaban Anda!

Ryan Williams

Saya berpikir bahwa seseorang mungkin ingin memperbaiki analisis saya, dan tidak menyadari bahwa Anda tidak mendapatkan reputasi dari wiki komunitas. Baiklah.

Janne H. Korhonen