{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:39:03Z","timestamp":1743154743097,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_23","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"271-282","source":"Crossref","is-referenced-by-count":3,"title":["Polynomial-Time Construction of Linear Network Coding"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudy","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Adler, M., Harvey, N.J., Jain, K., Kleinberg, R.D., Lehman, A.R.: On the capacity of information networks. In: Proc. 17th ACM-SIAM SODA, pp. 241\u2013250 (2006)","DOI":"10.1145\/1109557.1109585"},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"1204","DOI":"10.1109\/18.850663","volume":"46","author":"R. Ahlswede","year":"2000","unstructured":"Ahlswede, R., Cai, N., Li, S.-Y.R., Yeung, R.W.: Network information flow. IEEE Transactions on Information Theory\u00a046, 1204\u20131216 (2000)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"2745","DOI":"10.1109\/TIT.2005.851744","volume":"51","author":"R. Dougherty","year":"2005","unstructured":"Dougherty, R., Freiling, C., Zeger, K.: Insufficiency of linear coding in network information flow. IEEE Transactions on Information Theory\u00a051, 2745\u20132759 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"5067","DOI":"10.1109\/TIT.2006.883634","volume":"52","author":"R. Dougherty","year":"2006","unstructured":"Dougherty, R., Zeger, K.: Nonreversibility and equivalent constructions of multiple-unicast networks. IEEE Transactions on Information Theory\u00a052, 5067\u20135077 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci.\u00a010, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1109\/TIT.2005.864435","volume":"52","author":"C. Fragouli","year":"2006","unstructured":"Fragouli, C., Soljanin, E.: Information flow decomposition for network coding. IEEE Transactions on Information Theory\u00a052, 829\u2013848 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR7","unstructured":"Harvey, N.J., Karger, D.R., Murota, K.: Deterministic network coding by matrix completion. In: Proc. 16th ACM-SIAM SODA, pp. 489\u2013498 (2005)"},{"key":"23_CR8","unstructured":"Harvey, N.J., Kleinberg, R.D., Lehman, A.R.: Comparing network coding with multicommodity flow for the k-pairs communication problem. MIT LCS Technical Report 964 (September 2004)"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Ho, T., Karger, D.R., M\u00e9dard, M., Koetter, R.: Network coding from a network flow perspective. In: Proc. IEEE International Symposium on Information Theory (2003)","DOI":"10.1109\/ISIT.2003.1228458"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"1973","DOI":"10.1109\/TIT.2005.847712","volume":"51","author":"S. Jaggi","year":"2005","unstructured":"Jaggi, S., Sanders, P., Chou, P.A., Effros, M., Egner, S., Jain, K., Tolhuizen, L.M.G.M.: Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory\u00a051, 1973\u20131982 (2005)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR11","unstructured":"Koetter, R.: Network coding home page, http:\/\/tesla.csl.uiuc.edu\/~koetter\/NWC\/"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Koetter, R., M\u00e9dard, M.: Beyond routing: An algebraic approach to network coding. In: Proc. 21st Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 122\u2013130 (2002)","DOI":"10.1109\/INFCOM.2002.1019253"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Langberg, M., Sprintson, A., Bruck, J.: Network coding: A computational perspective. In: Proc. 40th Conference on Information Sciences and Systems (2006)","DOI":"10.1109\/CISS.2006.286590"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"2386","DOI":"10.1109\/TIT.2006.874434","volume":"52","author":"M. Langberg","year":"2006","unstructured":"Langberg, M., Sprintson, A., Bruck, J.: The encoding complexity of network coding. IEEE Transactions on Information Theory\u00a052, 2386\u20132397 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR15","unstructured":"Lehman, A.R.: Network Coding. PhD thesis. MIT, Cambridge (2005)"},{"key":"23_CR16","unstructured":"Lehman, A.R., Lehman, E.: Complexity classification of network information flow problems. In: Proc. 15th ACM-SIAM SODA, pp. 142\u2013150 (2004)"},{"key":"23_CR17","unstructured":"Lehman, A.R., Lehman, E.: Network coding: Does the model need tuning? In: Proc. 16th ACM-SIAM SODA, pp. 499\u2013504 (2005)"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1109\/TIT.2002.807285","volume":"49","author":"S.-Y.R. Li","year":"2003","unstructured":"Li, S.-Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Transactions on Information Theory\u00a049, 371\u2013381 (2003)","journal-title":"IEEE Transactions on Information Theory"},{"key":"23_CR19","unstructured":"M\u00e9dard, M., Effros, M., Ho, T., Karger, D.: On coding for non-multicast networks. In: Proc. 41st Annual Allerton Conference on Communication, Control and Computing (2003)"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-39658-1_44","volume-title":"Algorithms - ESA 2003","author":"A. Slivkins","year":"2003","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 482\u2013493. Springer, Heidelberg (2003)"},{"key":"23_CR21","unstructured":"Tavory, A., Feder, M., Ron, D.: Bounds on linear codes for network multicast. ECCC Technical Report 33 (2003)"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Wang, C.-C., Shroff, N.B.: Beyond the butterfly \u2013 A graph-theoretic characterization of the feasibility of network coding with two simple unicast sessions. In: Proc. IEEE International Symposium on Information Theory (2007)","DOI":"10.1109\/ISIT.2007.4557214"},{"key":"23_CR23","unstructured":"Wang, C.-C., Shroff, N.B.: Intersession network coding for two simple multicast sessions. In: Proc. 45th Annual Allerton Conference on Communication, Control and Computing (2007)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T12:13:14Z","timestamp":1738325594000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}