Some lower bounds on the Shannon capacity

• Autorzy: Jurkiewicz M. , Kubale M. , Turowski K.
• Języki publikacji: EN

Abstrakty

EN

In the paper we present a measure of a discrete noisy channel, named the Shannon capacity, which is described in the language of graph theory. Unfortunately, the Shannon capacity C0 is difficult to calculate, so we try to estimate the value of C0 for specific classes of graphs, i.e. circular graphs.

Słowa kluczowe

EN

Shannon capacity; circular graphs; information theory

PL

pojemność Shannona; graf kołowy; teoria informacji

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2014
• Tom: Vol. 22, nr 2
• Strony: 31--42
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Jurkiewicz M.

• Gdansk University of Technology, Department of Algorithms and Systems Modelling, Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Kubale M.

• Gdansk University of Technology, Department of Algorithms and Systems Modelling, Narutowicza 11/12, 80-233 Gdańsk, Poland

autor

Turowski K.

• Gdansk University of Technology, Department of Algorithms and Systems Modelling, Narutowicza 11/12, 80-233 Gdańsk, Poland

Bibliografia

• [1] Shannon, C. E., The zero error capacity of a noisy channel, Institute of Radio Engineers, Transactions on Information Theory, Vol. IT-2, No. September, 1956, pp. 8–19.
• [2] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, Vol. 25, No. 1, 1979, pp. 1–7.
• [3] Rosenfeld, M., On a problem of C. E. Shannon in graph theory, Proc. Amer. Math. Soc., Vol. 18, 1967, pp. 315–319.
• [4] Sonnemann, E. and Krafft, O., Independence numbers of product graphs, J. Combinatorial Theory Ser. B, Vol. 17, 1974, pp. 133–142.
• [5] Erdős, P., Ko, C., and Rado, R., Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2), Vol. 12, 1961, pp. 313–320.
• [6] Brimkov, V., Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Discrete Appl. Math., Vol. 155, No. 14, 2007, pp. 1812–1825.
• [7] Baumert, L. D., McEliece, R. J., Rodemich, E., Rumsey, J. H. C., Stanley, R., and Taylor, H., A combinatorial packing problem. Computers in algebra and number theory, In: Computers in algebra and number theory (Proc. SIAMAMS Sympos. Appl. Math., New York, 1970), Amer. Math. Soc., Providence, R.I., 1971, pp. 97–108.
• [8] Badalyan, S. H. and Markosyan, S. E., On the independence number of the strong product of cycle-powers, Discrete Math., Vol. 313, No. 1, 2013, pp. 105–110.
• [9] Jurkiewicz, M., Kubale, M., and Ocetkiewicz, K., On the Shannon capacity of circulant graphs, preprint.
• [10] Codenotti, B., Gerace, I., and Resta, G., Some remarks on the Shannon capacity of odd cycles, Ars Combin., Vol. 66, 2003, pp. 243–257.