4 ms·
If the algorithm's so short, why not post the pseudocode? Or did they? Here's my impression based on the article and a few minutes of refreshers: Problem: Gi
by SilasX 14y ago
If the algorithm's so short, why not post the pseudocode?
Or did they? Here's my impression based on the article and a few minutes of refreshers:
Problem: Given a (weighted?) graph, output its Laplacian matrix, which represents (in the sense of being polynominal-time reducible to?) how much current would flow between any two nodes if voltage were applied across it.
New algorithm:
1) Find a (minimal?) spanning tree for the graph.
2) Calculate how much current would flow through that graph if it were so weighted and a unit voltage were applied through it, with the edges being resistors (and leaves presumably connected to ground?).
3) Create a loop restoring one of the edges in the original graph.
4) Update the currents your previously calculated by the amount needed to balance the circuit.
5) Repeat from Step 2) until you have the original graph.
6) The currents are your solution?
(Sorry, lots of edits to correct and clarify.)
- pshc 14y agoThat's pretty much what I gleaned too. The paper specifies how an acceptable ("low-stretch") spanning tree is shaped, and bounds [something, error criterion?] as part of its complexity proof.
- SilasX 14y agoSo I guess the bulk of the brainwork in producing this result was in a) deriving the low-stretch spanning tree definition and algorithm, and b) proving the performance bound? Because, aside from understanding the low-stretch spanning tree calculation, the algorithm is indeed pretty simple. Actually, I should add: one other tricky is coming up with (the probability distribution for) how you choose the order in which to restore edges.
- sp332 14y agoThe first link under "Related" on the right is the paper itself. The "SimpleSolver" is at the top of page 8. http://arxiv.org/pdf/1301.6628.pdf http://arxiv.org/pdf/1301.6628.pdf
- Sniffnoy 14y agoA note -- when linking to arXiv, please link to the abstract, not directly to the PDF.
- deadairspace 14y agoWhy? The pdf is what I'm interested in. I don't particularly care where it's hosted.
- derleth 14y agoThere's more formats available, for one thing.
- LukeShu 14y agoFor the lazy: http://arxiv.org/abs/1301.6628 http://arxiv.org/abs/1301.6628
- imurray 14y agoI agree, but gave up trying to convince people. I now use a userscript to rewrite all arxiv pdf links (outside arxiv itself) to point to the corresponding abstract page: http://homepages.inf.ed.ac.uk/imurray2/code/user_scripts/arxiv_abs.user.js http://homepages.inf.ed.ac.uk/imurray2/code/user_scripts/arx...
- cdtwigg 14y agoOkay, so these papers are phrased a little confusingly, but what they're really doing is solving a specific but very useful type of linear equation Ax = b where A is a diagonally-dominant matrix (entries on the diagonal are larger than the sum of the off-diagonal entries). It happens that graphs are equivalent to matrices, so it's a neat area that straddles applied math and computer science. For a survey paper on recent developments in the field: http://www.cs.cmu.edu/~jkoutis/papers/CACM-KMP.pdf http://www.cs.cmu.edu/~jkoutis/papers/CACM-KMP.pdf
- Qantourisc 14y agoAAaa! the ant solution!