Connecting multiple-unicast and network error correction: Reduction and unachievability

Wentao Huang, Michael Langberg, Joerg Kliewer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We show that solving a multiple-unicast network coding problem can be reduced to solving a single-unicast network error correction problem, where an adversary may jam at most a single edge in the network. Specifically, we present an efficient reduction that maps a multiple-unicast network coding instance to a network error correction instance while preserving feasibility. The reduction holds for both the zero probability of error model and the vanishing probability of error model. Previous reductions are restricted to the zero-error case. As an application of the reduction, we present a constructive example showing that the single-unicast network error correction capacity may not be achievable, a result of separate interest.

Original languageEnglish (US)
Title of host publicationProceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages361-365
Number of pages5
ISBN (Electronic)9781467377041
DOIs
StatePublished - Sep 28 2015
Externally publishedYes
EventIEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong
Duration: Jun 14 2015Jun 19 2015

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2015-June
ISSN (Print)2157-8095

Other

OtherIEEE International Symposium on Information Theory, ISIT 2015
CountryHong Kong
CityHong Kong
Period6/14/156/19/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Connecting multiple-unicast and network error correction: Reduction and unachievability'. Together they form a unique fingerprint.

Cite this