Abstract:
We consider the problem of estimating the Shannon capacity of a circulant graph C_nj of degree four with n vertices and chord length j, , by computing its Lovasz theta function theta(C_nj ). Our interest in this problem is driven by possible applications to error-free communication of data describing the structure of a digital line. The latter can be represented in terms of spyrographs [12], which, as a matter of fact, are circulants of degree four. We present an algorithm for theta(C_nj ) computation 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.
Description:
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s).
