Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assume we have a graph, and resistors are placed on the edges. I want to know if there is an algorithm that find the total resistance between any 2 vertex. i have a hard time finding any description of such algorithm.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

I am very very rusty on this topic.

I remember that the node voltage method (which is just a shortcut over Kirchhoff's laws) involved only equations written on the nodes (no cycle equations). Therefore, you can easily generate the system of equations in linear time and then solve it (by Gaussian elimination) in cubic time in the number of nodes.

EDIT: Actually, I was feeling a bit bored, so here is a simple implementation (naive though).

share|improve this answer
    
Thanks for this solution @aelguindy , I implemented it in C++ . However the Matrix required to solve this is VXV as I understand it, where V= vertices in graph. VXV is too large , V=800k . Is there a solution that has better space complexity. –  Govinda Keshavdas Aug 26 at 18:22
    
@GovindaKeshavdas what you're looking at is a Laplacian matrix. There are several ways to approximate effective resistances (or equivalently the current flow). Read this cs.yale.edu/homes/spielman/PAPERS/icm10post.pdf –  aelguindy Aug 26 at 23:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.