On the multiple unicast network coding conjecture
In this paper, we study the multiple unicast network communication problem on undirected graphs. It has been conjectured by Li and Li [CISS 2004] that, for the problem at hand, the use of network coding does not allow any advantage over standard routing. Loosely speaking, we show that under certain...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/59589 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826192445775282176 |
|---|---|
| author | Langberg, Michael Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Langberg, Michael Medard, Muriel |
| author_sort | Langberg, Michael |
| collection | MIT |
| description | In this paper, we study the multiple unicast network communication problem on undirected graphs. It has been conjectured by Li and Li [CISS 2004] that, for the problem at hand, the use of network coding does not allow any advantage over standard routing. Loosely speaking, we show that under certain (strong) connectivity requirements the advantage of network coding is indeed bounded by 3. |
| first_indexed | 2024-09-23T09:12:18Z |
| format | Article |
| id | mit-1721.1/59589 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:12:18Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/595892022-09-30T14:03:15Z On the multiple unicast network coding conjecture Langberg, Michael Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel Medard, Muriel In this paper, we study the multiple unicast network communication problem on undirected graphs. It has been conjectured by Li and Li [CISS 2004] that, for the problem at hand, the use of network coding does not allow any advantage over standard routing. Loosely speaking, we show that under certain (strong) connectivity requirements the advantage of network coding is indeed bounded by 3. 2010-10-29T16:19:41Z 2010-10-29T16:19:41Z 2010-01 2009-09 Article http://purl.org/eprint/type/JournalArticle 978-1-4244-5870-7 INSPEC Accession Number: 11135244 http://hdl.handle.net/1721.1/59589 Langberg, M., and M. Medard. “On the multiple unicast network coding, conjecture.” Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. 2009. 222-227. ©2010 Institute of Electrical and Electronics Engineers. https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/ALLERTON.2009.5394800 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Langberg, Michael Medard, Muriel On the multiple unicast network coding conjecture |
| title | On the multiple unicast network coding conjecture |
| title_full | On the multiple unicast network coding conjecture |
| title_fullStr | On the multiple unicast network coding conjecture |
| title_full_unstemmed | On the multiple unicast network coding conjecture |
| title_short | On the multiple unicast network coding conjecture |
| title_sort | on the multiple unicast network coding conjecture |
| url | http://hdl.handle.net/1721.1/59589 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT langbergmichael onthemultipleunicastnetworkcodingconjecture AT medardmuriel onthemultipleunicastnetworkcodingconjecture |