{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T11:40:07Z","timestamp":1688211607809},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,4,27]],"date-time":"2013-04-27T00:00:00Z","timestamp":1367020800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s00453-013-9789-9","type":"journal-article","created":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T21:19:12Z","timestamp":1367356752000},"page":"152-180","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Time Algorithm for Min-Ranks of Graphs with Simple Tree Structures"],"prefix":"10.1007","volume":"71","author":[{"given":"Son Hoang","family":"Dau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yeow Meng","family":"Chee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,4,27]]},"reference":[{"key":"9789_CR1","doi-asserted-by":"crossref","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 Trans. Inf. Theory 46, 1204\u20131216 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9789_CR2","first-page":"197","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Z. Bar-Yossef","year":"2006","unstructured":"Bar-Yossef, Z., Birk, Z., Jayram, T.S., Kol, T.: Index coding with side information. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197\u2013206 (2006)"},{"key":"9789_CR3","first-page":"869","volume-title":"Proceedings of the IEEE Symposium on Information Theory (ISIT)","author":"Y. Berliner","year":"2011","unstructured":"Berliner, Y., Langberg, M.: Index coding with outerplanar side information. In: Proceedings of the IEEE Symposium on Information Theory (ISIT), Saint Petersburg, Russia, pp. 869\u2013873 (2011)"},{"key":"9789_CR4","unstructured":"Berliner, Y., Langberg, M.: Index coding with outerplanar side information. Manuscript (2011). Available at http:\/\/www.openu.ac.il\/home\/mikel\/papers\/outer.pdf"},{"key":"9789_CR5","first-page":"1257","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM)","author":"Y. Birk","year":"1998","unstructured":"Birk, Y., Kol, T.: Informed-source coding-on-demand (ISCOD) over broadcast channels. In: Proceedings of the IEEE Conference on Computer Communications (INFOCOM), San Francisco, CA, pp. 1257\u20131264 (1998)"},{"issue":"6","key":"9789_CR6","doi-asserted-by":"crossref","first-page":"2825","DOI":"10.1109\/TIT.2006.874540","volume":"52","author":"Y. Birk","year":"2006","unstructured":"Birk, Y., Kol, T.: Coding-on-demand by an informed source (ISCOD) for efficient broadcast of different supplemental data to caching clients. IEEE Trans. Inf. Theory 52(6), 2825\u20132830 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9789_CR7","first-page":"433","volume":"3","author":"G. Chartrand","year":"1967","unstructured":"Chartrand, G., Harary, F.: Planar permutation graphs. Ann. Inst. Henri Poincar\u00e9 B, Probab. Stat. 3(4), 433\u2013438 (1967)","journal-title":"Ann. Inst. Henri Poincar\u00e9 B, Probab. Stat."},{"key":"9789_CR8","first-page":"1","volume-title":"Proceedings of the IEEE Conference on Computer Communications (INFOCOM)","author":"M.A.R. Chaudhry","year":"2008","unstructured":"Chaudhry, M.A.R., Sprintson, A.: Efficient algorithms for index coding. In: Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pp. 1\u20134 (2008)"},{"key":"9789_CR9","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1137\/1.9781611973099.35","volume-title":"Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"E. Chlamtac","year":"2012","unstructured":"Chlamtac, E., Haviv, I.: Linear index coding via semidefinite programming. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 406\u2013419 (2012)"},{"key":"9789_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M. Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"9789_CR11","first-page":"20","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"G. Cornuejols","year":"2003","unstructured":"Cornuejols, G., Liu, X., Vuskovic, K.: A polynomial time algorithm for recognizing perfect graphs. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 20\u201327 (2003)"},{"key":"9789_CR12","doi-asserted-by":"crossref","unstructured":"Dau, S.H.: See web.spms.ntu.edu.sg\/~daus0001\/mr-small-graphs.html (2011)","DOI":"10.1515\/semi.2011.047"},{"key":"9789_CR13","unstructured":"Dau, S.H.: See web.spms.ntu.edu.sg\/~daus0001\/mr.html (2011)"},{"key":"9789_CR14","series-title":"Lecture Notes in Computer Science","first-page":"333","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability Testing. Lecture Notes in Computer Science, vol. 2919, pp. 333\u2013336. Springer, Berlin (2004)"},{"issue":"7","key":"9789_CR15","doi-asserted-by":"crossref","first-page":"3187","DOI":"10.1109\/TIT.2010.2048502","volume":"56","author":"S. El Rouayheb","year":"2010","unstructured":"El Rouayheb, S., Sprintson, A., Georghiades, C.: On the index coding problem and its relation to network coding and matroid theory. IEEE Trans. Inf. Theory 56(7), 3187\u20133195 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9789_CR16","first-page":"267","volume":"25","author":"W. Haemers","year":"1978","unstructured":"Haemers, W.: An upper bound for the Shannon capacity of a graph. Algebr. Methods Graph Theory 25, 267\u2013272 (1978)","journal-title":"Algebr. Methods Graph Theory"},{"key":"9789_CR17","first-page":"2231","volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","author":"I. Haviv","year":"2012","unstructured":"Haviv, I., Langberg, M.: On linear index coding for random graphs. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 2231\u20132235 (2012)"},{"issue":"4","key":"9789_CR18","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1151659.1159942","volume":"36","author":"S. Katti","year":"2006","unstructured":"Katti, S., Rahul, H., Hu, W., Katabi, D., M\u00e9dard, M., Crowcroft, J.: Xors in the air: practical wireless network coding. ACM SIGCOMM Comput. Commun. Rev. 36(4), 243\u2013254 (2006)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"issue":"4","key":"9789_CR19","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/1402946.1403004","volume":"38","author":"S. Katti","year":"2008","unstructured":"Katti, S., Katabi, D., Balakrishnan, H., M\u00e9dard, M.: Symbol-level network coding for wireless mesh networks. ACM SIGCOMM Comput. Commun. Rev. 38(4), 401\u2013412 (2008)","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"9789_CR20","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1109\/TNET.2003.818197","volume":"11","author":"R. Koetter","year":"2003","unstructured":"Koetter, R., M\u00e9dard, M.: An algebraic approach to network coding. IEEE\/ACM Tranans. Netw. 11, 782\u2013795 (2003)","journal-title":"IEEE\/ACM Tranans. Netw."},{"key":"9789_CR21","first-page":"315","volume-title":"Proceedings IEEE Symp. on Inform. Theory (ISIT)","author":"M. Langberg","year":"2008","unstructured":"Langberg, M., Sprintson, A.: On the hardness of approximating the network coding capacity. In: Proceedings IEEE Symp. on Inform. Theory (ISIT), Toronto, Canada, pp. 315\u2013319 (2008)"},{"key":"9789_CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9789_CR23","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1109\/FOCS.2007.48","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"E. Lubetzky","year":"2007","unstructured":"Lubetzky, E., Stav, U.: Non-linear index coding outperforming the linear optimum. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 161\u2013168 (2007)"},{"issue":"3","key":"9789_CR24","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/BF01261326","volume":"16","author":"R. Peeters","year":"1996","unstructured":"Peeters, R.: Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16(3), 417\u2013431 (1996)","journal-title":"Combinatorica"},{"key":"9789_CR25","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TIT.1956.1056774","volume":"3","author":"C.E. Shannon","year":"1956","unstructured":"Shannon, C.E.: The zero-error capacity of a noisy channel. IRE Trans. Inf. Theory 3, 3\u201315 (1956)","journal-title":"IRE Trans. Inf. Theory"},{"key":"9789_CR26","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Proces. Lett. 160\u2013161 (1974)","DOI":"10.1016\/0020-0190(74)90003-9"},{"key":"9789_CR27","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/3-540-17218-1_57","volume-title":"Proceedings of the International Workshop WG \u201986 on Graph-Theoretic Concepts in Computer Science","author":"M. Wiegers","year":"1987","unstructured":"Wiegers, M.: Recognizing outerplanar graphs in linear time. In: Proceedings of the International Workshop WG \u201986 on Graph-Theoretic Concepts in Computer Science, pp. 165\u2013176 (1987)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9789-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9789-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9789-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,1]],"date-time":"2023-07-01T11:06:18Z","timestamp":1688209578000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9789-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,27]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["9789"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9789-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,27]]}}}