{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:22:15Z","timestamp":1750306935893,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC-2009-StG-240317"],"award-info":[{"award-number":["ERC-2009-StG-240317"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["PP00P2128639"],"award-info":[{"award-number":["PP00P2128639"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts the signals and there is interference among transmissions. Recently, Avestimehr et al. [2007b] proposed a linear deterministic model that takes into account the shared nature of wireless channels, focusing on the signal interactions rather than the background noise. They generalized the min-cut max-flow theorem for graphs to networks of deterministic channels and proved that the capacity can be achieved using information theoretical tools. They showed that the value of the minimum cut is in this case the minimum rank of all the adjacency matrices describing source-destination cuts.<\/jats:p>\n          <jats:p>In this article, we develop a polynomial-time algorithm that discovers the relay encoding strategy to achieve the min-cut value in linear deterministic (wireless) networks, for the case of a unicast connection. Our algorithm crucially uses a notion of linear independence between channels to calculate the capacity in polynomial time. Moreover, we can achieve the capacity by using very simple one-symbol processing at the intermediate nodes, thereby constructively yielding finite-length strategies that achieve the unicast capacity of the linear deterministic (wireless) relay network.<\/jats:p>","DOI":"10.1145\/2390176.2390184","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Combinatiorial algorithms for wireless information flow"],"prefix":"10.1145","volume":"9","author":[{"given":"Javad B.","family":"Ebrahimi","sequence":"first","affiliation":[{"name":"EPFL, Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christina","family":"Fragouli","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,26]]},"reference":[{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Amaudruz A.","key":"e_1_2_1_1_1"},{"volume-title":"Proceedings of Allerton Conference on Communication, Control, and Computing. http:\/\/licos.epfl.ch\/index.php&quest;p=research_projWNC.","author":"Avestimehr S.","key":"e_1_2_1_2_1"},{"volume-title":"Proceedings of Allerton Conference on Communication, Control, and Computing. http:\/\/licos. epfl.ch\/index.php&quest;p=research_projWNC.","author":"Avestimehr S.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the Information Theory Workshop (ITW).","author":"Ebrahimi J. B.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing","author":"Ebrahimi J. B.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094930"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing.","author":"Goemans M.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing.","author":"Kim M.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","unstructured":"Shi C. and Ramamoorthy A. 2010. Fast algorithms for finding unicast capacity of linear deterministic wireless relay networks. arXiv:0909.5507v1.  Shi C. and Ramamoorthy A. 2010. Fast algorithms for finding unicast capacity of linear deterministic wireless relay networks. arXiv:0909.5507v1."},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Tabatabaei Yazdi S.","key":"e_1_2_1_12_1"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390184","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2390176.2390184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:44Z","timestamp":1750235744000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2390176.2390184"],"URL":"https:\/\/doi.org\/10.1145\/2390176.2390184","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}