Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
We introduce a new approach to computing an approximately maximum s-t flow in a capacitated, undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be...
| Những tác giả chính: | , , , , |
|---|---|
| Tác giả khác: | |
| Định dạng: | Bài viết |
| Ngôn ngữ: | en_US |
| Được phát hành: |
Association for Computing Machinery
2012
|
| Truy cập trực tuyến: | http://hdl.handle.net/1721.1/71698 https://orcid.org/0000-0003-0536-0323 https://orcid.org/0000-0002-4257-4198 |