Analyse de la complexité temporelle pour l'algorithme UST-CONN de Reingold

Quelle est la complexité temporelle exacte de l' algorithme d'espace de journalisation st-connectivité non orienté d'Omer Reingold?

cc.complexity-theory randomness Suresh Venkat
la source

Veuillez être plus précis. Décrivez votre question de manière suffisamment détaillée et citez les références appropriées.

MS Dousti

Je pense que la question est assez claire: doi.acm.org/10.1145/1391289.1391291 est le papier.

András Salamon

La question est assez claire pour ceux qui travaillent dans la région, mais c'est probablement une bonne idée de demander aux affiches de donner plus d'informations pour qu'un public plus large puisse comprendre la question.

Robin Kothari

Réponses:

Il semble que la complexité temporelle de l'algorithme de Reingold ne soit traitée ni dans l'article de Reingold ni dans le manuel Arora-Barak. Il semblerait également que l'analyse soit plutôt fastidieuse, car la complexité temporelle dépend du graphique d'expansion exact utilisé dans la construction et de certaines constantes choisies comme "suffisamment grandes".

$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
la source

la prochaine fois, ne marquez pas votre réponse comme wiki communautaire. Sinon, vous n'obtiendrez pas de crédit pour votre réponse!

Ryan Williams

Je pensais que quelqu'un voudrait peut-être affiner mon analyse et je ne savais pas que les wikis de la communauté ne faisaient pas leur réputation. Tant pis.

Janne H. Korhonen du