DocumentCode
1779909
Title
Multicasting in linear deterministic relay network by matrix completion
Author
Soma, T.
Author_Institution
Grad. Sch. of Inf. Sci. & Technol., Univ. of Tokyo, Tokyo, Japan
fYear
2014
fDate
June 29 2014-July 4 2014
Firstpage
1191
Lastpage
1195
Abstract
We provide a faster deterministic polynomial time algorithm for multicasting in a linear deterministic relay network, a wireless communication framework proposed by Avestimehr, Diggavi and Tse (2011). The running time of our algorithm matches the current best complexity of unicast computations for each sink. Our approach is based on the polylinking flow model of Goemans, Iwata and Zenklusen (2012), and the mixed matrix completion technique of Harvey, Karger and Murota (2005).
Keywords
multicast communication; polynomials; relay networks (telecommunication); wireless channels; deterministic polynomial time algorithm; linear deterministic relay network; mixed matrix completion; multicasting; polylinking flow model; unicast computations; wireless communication framework; Algorithm design and analysis; Complexity theory; Encoding; Matrices; Network coding; Relay networks (telecommunications); Unicast;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory (ISIT), 2014 IEEE International Symposium on
Conference_Location
Honolulu, HI
Type
conf
DOI
10.1109/ISIT.2014.6875021
Filename
6875021
Link To Document