×

Algorithmic and explicit determination of the Lovász number for certain circulant graphs. (English) Zbl 1123.05085

Summary: We consider the problem of computing the Lovász theta function for circulant graphs \(C_{n,J}\) of degree four with \(n\) vertices and chord length \(J\), \(2 \leqslant J \leqslant n\). We present an algorithm that takes \(O(J)\) operations if \(J\) is an odd number, and \(O(n/J)\) operations if \(J\) is even. On the considered class of graphs our algorithm strongly outperforms the known algorithms for theta function computation. We also provide explicit formulas for the important special cases \(J = 2\) and \(J = 3\).

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
94A40 Channel models (including quantum) in information and communication theory

Software:

SDPpack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adám, A., Research problem 2-10, J. Combin. Theory, 393, 1109-1124 (1991)
[2] Alizadeh, F., Interior point methods in semidefinite programming with applications to combinatorial optimization, SIAM J. Optim., 5, 1, 13-51 (1995) · Zbl 0833.90087
[3] F. Alizadeh et al., SDPPACK user’s guide, \( \langle;\) http://www.cs.nyu.edu/faculty/overton/sdppack,sdppack.html \(\rangle;\).; F. Alizadeh et al., SDPPACK user’s guide, \( \langle;\) http://www.cs.nyu.edu/faculty/overton/sdppack,sdppack.html \(\rangle;\).
[4] Alon, N., On the capacity of digraphs, European J. Combin., 19, 1-5 (1998) · Zbl 0894.05031
[5] Alon, N.; Orlitsky, A., Repeated communication and Ramsey graphs, IEEE Trans. Inform. Theory, 33, 1276-1289 (1995) · Zbl 0831.94003
[6] Ashley, J. J.; Siegel, P. H., A note on the Shannon Capacity of run-length-limited codes, IEEE Trans. Inform. Theory, IT-33, 601-605 (1987) · Zbl 0631.94005
[7] Beivide, R.; Herrada, E.; Balcázar, J. L.; Arruabarrena, A., Optimal distance networks of low degree for parallel computers, IEEE Trans. Comput., C-30, 10, 1109-1124 (1991) · Zbl 1395.68024
[8] Berge, C., Graphs (1985), North-Holland Mathematical Library · Zbl 0334.05117
[9] Bermond, J.-C.; Comellas, F.; Hsu, D. F., Distributed loop computer networks: A survey, J. Parallel Distributed Comput., 24, 2-10 (1995)
[10] Bouknight, W. J.; Denenberg, S. A.; McIntyre, D. E.; Randall, J. M.; Samel, A. H.; Slotnick, D. L., Proc. IEEE, 60, 4, 369-378 (1972)
[11] Dorst, L.; Duin, R. P.W., Spirograph theory: a framework for calculations on digitized straight lines, IEEE Trans. Pattern Anal. Mach. Intell., 6, 632-639 (1984) · Zbl 0545.68098
[12] Farber, M., An analogue of the Shannon capacity of a graph, SIAM J. Algebraic Discrete Methods, 7, 67-72 (1986) · Zbl 0717.05070
[13] U. Feige, Randomized graph products, chromatic numbers, and the Lovász \(\operatorname{\Theta;} \)-function, in: Proceedings of the 27th STOC, 1995, pp. 635-640.; U. Feige, Randomized graph products, chromatic numbers, and the Lovász \(\operatorname{\Theta;} \)-function, in: Proceedings of the 27th STOC, 1995, pp. 635-640. · Zbl 1058.94517
[14] Goemans, M. X.; Rendl, F., Semidefinite programs and association schemes, Computing, 63, 331-340 (1999) · Zbl 0956.90029
[15] Haemers, W., An upper bound for the Shannon capacity of a graph, Colloq. Math. Soc. János Bolyai, 25, 267-272 (1978)
[16] Huber, K., Codes over tori, IEEE Trans. Inform. Theory, 43, 2, 740-744 (1997) · Zbl 0870.94048
[17] Knuth, D. E., The sandwich theorem, Electron. J. Combin., 1, 1-48 (1994)
[18] Leighton, F. T., Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes (1996), M. Kaufmann: M. Kaufmann Los Altos, CA
[19] B. Liton, B. Mans, On isomorphic chordal rings, in: Proceedings of the Seventh Australian Workshop on Combinatorial Algorithms, AWOCA’96, University of Sydney, BDCS-TR-508, 1996, pp. 108-111.; B. Liton, B. Mans, On isomorphic chordal rings, in: Proceedings of the Seventh Australian Workshop on Combinatorial Algorithms, AWOCA’96, University of Sydney, BDCS-TR-508, 1996, pp. 108-111.
[20] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25, 1-7 (1979) · Zbl 0395.94021
[21] Mans, B., Optimal distributed algorithms in unlabeled tori and chordal rings, J. Parallel Distributed Comput., 46, 1, 80-90 (1997) · Zbl 0896.68064
[22] Megiddo, N., Linear programming in linear time when the dimension is fixed, J. ACM, 31, 1, 114-127 (1984) · Zbl 0637.90064
[23] Minc, H., Permanental compounds and permanents of (0,1) circulants, Linear Algebra Appl., 86, 11-46 (1987) · Zbl 0608.15009
[24] O’Rourke, J., Computational Geometry in C (1994), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0816.68124
[25] Rosenfeld, M., On a problem of Shannon, Proc. Amer. Math. Soc., 18, 315-319 (1967) · Zbl 0147.42801
[26] Shannon, C. E., The zero-error capacity of a noisy channel, IRE Trans. Inform. Theory, IT-2, 8-19 (1956)
[27] Wilkov, R. S., Analysis and design of reliable computer networks, IEEE Trans. Comm., 20, 660-678 (1972)
[28] Wong, C. K.; Coppersmith, D., A combinatorial problem related to multimodule memory organization, J. ACM, 21, 3, 392-402 (1974) · Zbl 0353.68039
[29] Yang, Y.; Funashashi, A.; Jouraku, A.; Nishi, H.; Amano, H.; Sueyoshi, T., Recursive diagonal torus: an interconnection network for massively parallel computers, IEEE Trans. Parallel Distributed Systems, 12, 7, 701-715 (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.