Fluxo elétrico plano exato

22

Considere uma rede elétrica modelada como um gráfico planar G, em que cada aresta representa um resistor de 1Ω. Com que rapidez podemos calcular a resistência efetiva exata entre dois vértices em G? Equivalentemente, com que rapidez podemos calcular a corrente exata que flui ao longo de cada extremidade, se conectarmos uma bateria de 1V a dois vértices em G?

As conhecidas leis de tensão e corrente de Kirchhoff reduzem esse problema para resolver um sistema de equações lineares com uma variável por aresta. Resultados mais recentes - descritos explicitamente por Klein e Randić (1993), mas implícitos em trabalhos anteriores de Doyle e Snell (1984) - reduzem o problema à solução de um sistema linear com uma variável por vértice, representando o potencial desse nó ; a matriz para este sistema linear é a matriz laplaciana do gráfico.

De qualquer sistema linear pode ser resolvido exatamente em do tempo utilizando uma dissecção aninhada e separadores planares [ Lipton Rose Tarjan 1979 ]. Esse é o algoritmo mais rápido conhecido?O(n3/2)

Resultados seminais recentes de Spielman, Teng e outros sugerem que o sistema laplaciano em gráficos arbitrários pode ser resolvido aproximadamente em tempo quase linear. Veja [ Koutis Miller Peng 2010 ] para saber o melhor tempo de execução atual e este incrível artigo de Erica Klarreich na Fundação Simons para uma visão geral de alto nível. Mas estou especificamente interessado em algoritmos exatos para gráficos planares .

Suponha um modelo de computação que suporte aritmética real exata em tempo constante.

Jeffε
fonte
o artigo de Klarreich menciona aplicações no fluxo máximo (otimização) próximo ao fim e já está desatualizado devido à recente inovação do Orlin , que aparentemente não está relacionada à direção de ataque do Laplaciano. veja também esta pergunta recente do tcs.se: Algum dos algoritmos de fluxo máximo de última geração é prático? O(mn)
vzn

Respostas:

14

O(nω)

O(nω)

A.Schulz
fonte