Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420922 | Discrete Applied Mathematics | 2007 | 14 Pages |
Abstract
We consider the problem of computing the Lovász theta function for circulant graphs Cn,JCn,J of degree four with nn vertices and chord length JJ, 2⩽J⩽n2⩽J⩽n. We present an algorithm that takes O(J)O(J) operations if JJ is an odd number, and O(n/J)O(n/J) operations if JJ 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=2J=2 and J=3J=3.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Valentin Brimkov,