Electric routing and concurrent flow cutting
We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the operator norm of the inverse graph Laplacian. We show how this norm...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Elsevier
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115843 https://orcid.org/0000-0002-4257-4198 |
| _version_ | 1826206986427957248 |
|---|---|
| author | Kelner, Jonathan Adam Maymounkov, Petar Borissov |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kelner, Jonathan Adam Maymounkov, Petar Borissov |
| author_sort | Kelner, Jonathan Adam |
| collection | MIT |
| description | We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the operator norm of the inverse graph Laplacian. We show how this norm reflects both latency and congestion of electric routing. Keywords: Oblivious routing; Spectral graph theory; Laplacian operator |
| first_indexed | 2024-09-23T13:41:43Z |
| format | Article |
| id | mit-1721.1/115843 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:41:43Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1158432022-10-01T16:35:13Z Electric routing and concurrent flow cutting Kelner, Jonathan Adam Maymounkov, Petar Borissov Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kelner, Jonathan Adam Maymounkov, Petar Borissov We investigate an oblivious routing scheme, amenable to distributed computation and resilient to graph changes, based on electrical flow. Our main technical contribution is a new rounding method which we use to obtain a bound on the operator norm of the inverse graph Laplacian. We show how this norm reflects both latency and congestion of electric routing. Keywords: Oblivious routing; Spectral graph theory; Laplacian operator 2018-05-24T15:45:24Z 2018-05-24T15:45:24Z 2010-06 2018-05-24T13:30:35Z Article http://purl.org/eprint/type/JournalArticle 0304-3975 http://hdl.handle.net/1721.1/115843 Kelner, Jonathan and Petar Maymounkov. “Electric Routing and Concurrent Flow Cutting.” Theoretical Computer Science 412, 32 (July 2011): 4123–4135 © 2010 Elsevier B.V. https://orcid.org/0000-0002-4257-4198 http://dx.doi.org/10.1016/j.tcs.2010.06.013 Theoretical Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Elsevier arXiv |
| spellingShingle | Kelner, Jonathan Adam Maymounkov, Petar Borissov Electric routing and concurrent flow cutting |
| title | Electric routing and concurrent flow cutting |
| title_full | Electric routing and concurrent flow cutting |
| title_fullStr | Electric routing and concurrent flow cutting |
| title_full_unstemmed | Electric routing and concurrent flow cutting |
| title_short | Electric routing and concurrent flow cutting |
| title_sort | electric routing and concurrent flow cutting |
| url | http://hdl.handle.net/1721.1/115843 https://orcid.org/0000-0002-4257-4198 |
| work_keys_str_mv | AT kelnerjonathanadam electricroutingandconcurrentflowcutting AT maymounkovpetarborissov electricroutingandconcurrentflowcutting |