Flux électrique planaire exact

22

Considérons un réseau électrique modélisé comme un graphe planaire G, où chaque front représente une résistance de 1Ω. À quelle vitesse peut-on calculer la résistance effective exacte entre deux sommets en G? De manière équivalente, à quelle vitesse pouvons-nous calculer le courant exact circulant le long de chaque bord si nous attachons une batterie 1V à deux sommets en G?

Les lois bien connues de la tension et du courant de Kirchhoff réduisent ce problème à la résolution d'un système d'équations linéaires avec une variable par bord. Résultats plus récents - décrits explicitement par Klein et Randić (1993) mais implicites dans les travaux antérieurs de Doyle et Snell (1984) - réduisent le problème à la résolution d'un système linéaire avec une variable par sommet, représentant le potentiel de ce nœud ; la matrice de ce système linéaire est la matrice laplacienne du graphe.

Soit le système linéaire peut être résolu exactement en O(n3/2) fois en utilisant la dissection emboîtée et séparateurs planaires [ Lipton Rose Tarjan 1979 ]. Est-ce l'algorithme le plus rapide connu?

Les résultats séminaux récents de Spielman, Teng et d'autres impliquent que le système laplacien dans les graphes arbitraires peut être résolu approximativement en temps quasi-linéaire. Voir [ Koutis Miller Peng 2010 ] pour le meilleur temps de course actuel, et cet article étonnant par Erica Klarreich à la Fondation Simons pour un aperçu de haut niveau. Mais je m'intéresse spécifiquement aux algorithmes exacts pour les graphes planaires .

Supposons un modèle de calcul qui prend en charge l'arithmétique réelle exacte en temps constant.

Jeffε
la source
l'article de Klarreich mentionne des applications dans (l'optimisation) du débit max près de la fin et est déjà obsolète en raison de la récente percée d' Orlin , qui n'est apparemment pas liée à la direction d'attaque laplacienne. voir aussi cette récente question sur tcs.se: certains des algorithmes de débit maximal de pointe sont-ils pratiques? O(mn)
vzn

Réponses:

14

O(nω)

O(nω)

A.Schulz
la source