Single-source/sink network error correction is as hard as multiple-unicast

Wentao Huang, Tracey Ho, Michael Langberg, Joerg Kliewer

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

2 Scopus citations

Abstract

We study the problem of communicating over a single-source single-terminal network in the presence of an adversary that may jam a single link of the network. If any one of the edges can be jammed, the capacity of such networks is well understood and follows directly from the connection between the minimum cut and maximum flow in single-source singleterminal networks. In this work we consider networks in which some edges cannot be jammed, and show that determining the network communication capacity is at least as hard as solving the multiple-unicast network coding problem for the error-free case. The latter problem is a long standing open problem.

Original languageEnglish (US)
Title of host publication2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages423-430
Number of pages8
ISBN (Electronic)9781479980093
DOIs
StatePublished - Jan 30 2014
Event2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014 - Monticello, United States
Duration: Sep 30 2014Oct 3 2014

Publication series

Name2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014

Other

Other2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014
CountryUnited States
CityMonticello
Period9/30/1410/3/14

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Single-source/sink network error correction is as hard as multiple-unicast'. Together they form a unique fingerprint.

Cite this