Algorithmic and explicit determination of the Lovász number for certain circulant graphs |
| |
Authors: | Valentin Brimkov |
| |
Affiliation: | Mathematics Department, SUNY Buffalo State College, Buffalo, NY 14222, USA |
| |
Abstract: | We consider the problem of computing the Lovász theta function for circulant graphs Cn,J of degree four with n vertices and chord length J, 2?J?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. |
| |
Keywords: | Shannon capacity Lová sz theta-function Circulant graph Linear programming |
本文献已被 ScienceDirect 等数据库收录! |
|