{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:17Z","timestamp":1740122357070,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T00:00:00Z","timestamp":1635811200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.<\/jats:p>","DOI":"10.1007\/s10878-021-00825-y","type":"journal-article","created":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T21:02:46Z","timestamp":1635886966000},"page":"2963-2980","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On zero-error codes produced by greedy algorithms"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9165-3028","authenticated-orcid":false,"given":"Marcin","family":"Jurkiewicz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,2]]},"reference":[{"key":"825_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-81-322-1599-8","volume-title":"Basic modern algebra with applications","author":"MR Adhikari","year":"2014","unstructured":"Adhikari MR, Adhikari A (2014) Basic modern algebra with applications. Springer, New Delhi. https:\/\/doi.org\/10.1007\/978-81-322-1599-8"},{"issue":"5","key":"825_CR2","doi-asserted-by":"publisher","first-page":"2172","DOI":"10.1109\/TIT.2006.872856","volume":"52","author":"N Alon","year":"2006","unstructured":"Alon N, Lubetzky E (2006) The Shannon capacity of a graph and the independence numbers of its powers. IEEE Trans Inf Theory 52(5):2172\u20132176. https:\/\/doi.org\/10.1109\/TIT.2006.872856","journal-title":"IEEE Trans Inf Theory"},{"issue":"1\u20132","key":"825_CR3","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ipl.2011.10.011","volume":"112","author":"MD Barrus","year":"2012","unstructured":"Barrus MD (2012) Havel\u2013Hakimi residues of unigraphs. Inf Process Lett 112(1\u20132):44\u201348. https:\/\/doi.org\/10.1016\/j.ipl.2011.10.011","journal-title":"Inf Process Lett"},{"key":"825_CR4","unstructured":"Baumert LD, McEliece RJ, Rodemich E, Rumsey HC Jr, Stanley R, Taylor H (1971) A combinatorial packing problem. In: Computers in algebra and number theory (Proc SIAM-AMS Sympos Appl Math, New York, 1970). American Mathematical Society, Providence, RI, pp 97\u2013108. SIAM\u2013AMS Proc., Vol. IV"},{"key":"825_CR5","doi-asserted-by":"crossref","unstructured":"Boche H, Deppe C (2020) Computability of the zero-error capacity of noisy channels. arXiv: 2010.06873","DOI":"10.1109\/ISIT44484.2020.9173984"},{"key":"825_CR6","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.dam.2013.12.011","volume":"182","author":"P Borowiecki","year":"2015","unstructured":"Borowiecki P, Rautenbach D (2015) New potential functions for greedy independence and coloring. Discrete Appl Math 182:61\u201372. https:\/\/doi.org\/10.1016\/j.dam.2013.12.011","journal-title":"Discrete Appl Math"},{"key":"825_CR7","doi-asserted-by":"crossref","unstructured":"Chalupa D, Posp\u00edchal J (2014) On the growth of large independent sets in scale-free networks. In: Nostradamus 2014: prediction, modeling and analysis of complex systems. Springer, pp 251\u2013260","DOI":"10.1007\/978-3-319-07401-6_24"},{"key":"825_CR8","first-page":"243","volume":"66","author":"B Codenotti","year":"2003","unstructured":"Codenotti B, Gerace I, Resta G (2003) Some remarks on the Shannon capacity of odd cycles. Ars Combin 66:243\u2013257","journal-title":"Ars Combin"},{"key":"825_CR9","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. MIT Press, Cambridge","edition":"3"},{"key":"825_CR10","volume-title":"Elements of information theory","author":"TM Cover","year":"2006","unstructured":"Cover TM, Thomas JA (2006) Elements of information theory, vol 2. Wiley, Hoboken"},{"key":"825_CR11","doi-asserted-by":"publisher","unstructured":"Csisz\u00e1r I, K\u00f6rner J (2011) Information theory, coding theorems for discrete memoryless systems, 2nd edn. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511921889","DOI":"10.1017\/CBO9780511921889"},{"issue":"1","key":"825_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1002\/jgt.3190150107","volume":"15","author":"O Favaron","year":"1991","unstructured":"Favaron O, Mah\u00e9o M, Sacl\u00e9 JF (1991) On the residue of a graph. J Graph Theory 15(1):39\u201364. https:\/\/doi.org\/10.1002\/jgt.3190150107","journal-title":"J Graph Theory"},{"key":"825_CR13","doi-asserted-by":"publisher","unstructured":"Favaron O, Mah\u00e9o M, Sacl\u00e9 JF (1993) Some eigenvalue properties in graphs (conjectures of Graffiti. II). Discrete Math 111(1-3):197\u2013220, graph theory and combinatorics (Marseille-Luminy, 1990). https:\/\/doi.org\/10.1016\/0012-365X(93)90156-N","DOI":"10.1016\/0012-365X(93)90156-N"},{"key":"825_CR14","doi-asserted-by":"publisher","unstructured":"Fomin FV, Kratsch D (2010) Exact exponential algorithms. Texts in theoretical computer science. An EATCS Series, Springer, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-642-16533-7","DOI":"10.1007\/978-3-642-16533-7"},{"key":"825_CR15","volume-title":"An atlas of fullerenes","author":"PW Fowler","year":"2007","unstructured":"Fowler PW, Manolopoulos D (2007) An atlas of fullerenes. Courier Corporation, North Chelmsford"},{"issue":"1","key":"825_CR16","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cplett.2007.09.054","volume":"448","author":"P Fowler","year":"2007","unstructured":"Fowler P, Daugherty S, Myrvold W (2007) Independence number and fullerene stability. Chem Phys Lett 448(1):75\u201382. https:\/\/doi.org\/10.1016\/j.cplett.2007.09.054","journal-title":"Chem Phys Lett"},{"key":"825_CR17","series-title":"Discrete mathematics and its applications (Boca Raton)","volume-title":"Handbook of graph theory","year":"2014","unstructured":"Gross JL, Yellen J, Zhang P (eds) (2014) Handbook of graph theory, 2nd edn. Discrete mathematics and its applications (Boca Raton). CRC Press, Boca Raton","edition":"2"},{"issue":"5","key":"825_CR18","doi-asserted-by":"publisher","first-page":"1155","DOI":"10.1016\/j.jctb.2012.06.001","volume":"102","author":"A Gy\u00e1rf\u00e1s","year":"2012","unstructured":"Gy\u00e1rf\u00e1s A, Seb\u0151 A, Trotignon N (2012) The chromatic gap and its extremes. J Comb Theory Ser B 102(5):1155\u20131178. https:\/\/doi.org\/10.1016\/j.jctb.2012.06.001","journal-title":"J Comb Theory Ser B"},{"key":"825_CR19","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1016\/0095-8956(73)90014-2","volume":"15","author":"RS Hales","year":"1973","unstructured":"Hales RS (1973) Numerical invariants and the strong product of graphs. J Comb Theory Ser B 15:146\u2013155","journal-title":"J Comb Theory Ser B"},{"key":"825_CR20","doi-asserted-by":"crossref","unstructured":"Hammack R, Imrich W, Klav\u017ear S (2011) Handbook of product graphs, 2nd edn. Discrete mathematics and its applications (Boca Raton). CRC Press, Boca Raton, FL, with a foreword by Peter Winkler","DOI":"10.1201\/b10959"},{"issue":"1\u20133","key":"825_CR21","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0012-365X(00)00298-3","volume":"232","author":"J Harant","year":"2001","unstructured":"Harant J, Schiermeyer I (2001) On the independence number of a graph in terms of order and size. Discrete Math 232(1\u20133):131\u2013138. https:\/\/doi.org\/10.1016\/S0012-365X(00)00298-3","journal-title":"Discrete Math"},{"key":"825_CR22","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.amc.2017.06.025","volume":"315","author":"M Jurkiewicz","year":"2017","unstructured":"Jurkiewicz M (2017) Average distance is submultiplicative and subadditive with respect to the strong product of graphs. Appl Math Comput 315:278\u2013285. https:\/\/doi.org\/10.1016\/j.amc.2017.06.025","journal-title":"Appl Math Comput"},{"key":"825_CR23","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-030-64843-5_7","volume-title":"Combinatorial optimization and applications","author":"M Jurkiewicz","year":"2020","unstructured":"Jurkiewicz M (2020) An approximation of the zero error capacity by a greedy algorithm. In: Wu W, Zhang Z (eds) Combinatorial optimization and applications. Springer, Cham, pp 91\u2013104"},{"key":"825_CR24","unstructured":"Jurkiewicz M, Pikies T (2015) Selected topics in modern mathematics, Publishing House AKAPIT, Krak\u00f3w, inst. Politechnika Krakowska, chap Some classical lower bounds on the independence number and their behavior on the strong product of graphs"},{"issue":"2","key":"825_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1515\/fcds-2015-0009","volume":"40","author":"M Jurkiewicz","year":"2015","unstructured":"Jurkiewicz M, Kubale M, Ocetkiewicz K (2015) On the independence number of some strong products of cycle-powers. Found Comput Decis Sci 40(2):133\u2013141. https:\/\/doi.org\/10.1515\/fcds-2015-0009","journal-title":"Found Comput Decis Sci"},{"issue":"6","key":"825_CR26","doi-asserted-by":"publisher","first-page":"2207","DOI":"10.1109\/18.720537","volume":"44","author":"J K\u00f6rner","year":"1998","unstructured":"K\u00f6rner J, Orlitsky A (1998) Zero-error information theory. IEEE Trans Inf Theory 44(6):2207\u20132229. https:\/\/doi.org\/10.1109\/18.720537","journal-title":"IEEE Trans Inf Theory"},{"key":"825_CR27","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/352","volume-title":"Graph colorings, contemporary mathematics","author":"M Kubale","year":"2004","unstructured":"Kubale M (2004) Graph colorings, contemporary mathematics, vol 352. American Mathematical Society, Providence. https:\/\/doi.org\/10.1090\/conm\/352"},{"key":"825_CR28","first-page":"985","volume":"11","author":"J Leskovec","year":"2010","unstructured":"Leskovec J, Chakrabarti D, Kleinberg J, Faloutsos C, Ghahramani Z (2010) Kronecker graphs: an approach to modeling networks. J Mach Learn Res 11:985\u20131042","journal-title":"J Mach Learn Res"},{"key":"825_CR29","series-title":"Discrete mathematics and its applications (Boca Raton)","doi-asserted-by":"publisher","DOI":"10.1201\/b17376","volume-title":"Bijective combinatorics","author":"NA Loehr","year":"2011","unstructured":"Loehr NA (2011) Bijective combinatorics. Discrete mathematics and its applications (Boca Raton). CRC Press, Boca Raton"},{"issue":"1","key":"825_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz L (1979) On the Shannon capacity of a graph. IEEE Trans Inf Theory 25(1):1\u20137. https:\/\/doi.org\/10.1109\/TIT.1979.1055985","journal-title":"IEEE Trans Inf Theory"},{"issue":"1\u20132","key":"825_CR31","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s10623-016-0194-7","volume":"84","author":"KA Mathew","year":"2017","unstructured":"Mathew KA, \u00d6sterg\u00e5rd PRJ (2017) New lower bounds for the Shannon capacity of odd cycles. Des Codes Cryptogr 84(1\u20132):13\u201322. https:\/\/doi.org\/10.1007\/s10623-016-0194-7","journal-title":"Des Codes Cryptogr"},{"key":"825_CR32","doi-asserted-by":"publisher","unstructured":"McEliece RJ (2004) The theory of information and coding, encyclopedia of mathematics and its applications, with a foreword by Mark Kac, vol 86. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511819896","DOI":"10.1017\/CBO9780511819896"},{"key":"825_CR33","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.ipl.2018.11.006","volume":"143","author":"SC Polak","year":"2019","unstructured":"Polak SC, Schrijver A (2019) New lower bound on the Shannon capacity of $$C_7$$ from circular graphs. Inf Process Lett 143:37\u201340. https:\/\/doi.org\/10.1016\/j.ipl.2018.11.006","journal-title":"Inf Process Lett"},{"key":"825_CR34","doi-asserted-by":"publisher","first-page":"315","DOI":"10.2307\/2035288","volume":"18","author":"M Rosenfeld","year":"1967","unstructured":"Rosenfeld M (1967) On a problem of C. E. Shannon in graph theory. Proc Am Math Soc 18:315\u2013319. https:\/\/doi.org\/10.2307\/2035288","journal-title":"Proc Am Math Soc"},{"key":"825_CR35","unstructured":"Scheinerman ER, Ullman DH (2011) Fractional graph theory. Dover Publications, Inc., Mineola, NY, a rational approach to the theory of graphs, With a foreword by Claude Berge, Reprint of the 1997 original"},{"issue":"September","key":"825_CR36","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/TIT.1956.1056798","volume":"2","author":"CE Shannon","year":"1956","unstructured":"Shannon CE (1956) The zero error capacity of a noisy channel. Trans Inf Theory IT 2(September):8\u201319","journal-title":"Trans Inf Theory IT"},{"key":"825_CR37","doi-asserted-by":"publisher","unstructured":"Whang JJ, Gleich DF, Dhillon IS (2013) Overlapping community detection using seed set expansion. In: Proceedings of the 22nd ACM international conference on information and knowledge management, association for computing machinery, New York, NY, USA, CIKM \u201913, p 2099\u20132108. https:\/\/doi.org\/10.1145\/2505515.2505535","DOI":"10.1145\/2505515.2505535"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00825-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00825-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00825-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:23:39Z","timestamp":1665779019000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00825-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,2]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["825"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00825-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,11,2]]},"assertion":[{"value":"5 October 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}