by Brimkov, VE, Barneva, RP, Klette, R and Straight, J
Abstract:
We consider the problem of estimating the Shannon capacity of a circulant graph Cn,j of degree four with n vertices and chord length J, 2 ≤ J ≤ n, by computing its Lovász theta function θ(C n,j). 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. © Springer-Verlag 2004.
Reference:
Efficient computation of the lovász theta function for a class of circulant graphs (Brimkov, VE, Barneva, RP, Klette, R and Straight, J), In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 3353, 2004.
Bibtex Entry:
@article{brimkov2004efficientgraphs,
author = "Brimkov, VE and Barneva, RP and Klette, R and Straight, J",
journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "285--295",
title = "Efficient computation of the lovász theta function for a class of circulant graphs",
volume = "3353",
year = "2004",
abstract = "We consider the problem of estimating the Shannon capacity of a circulant graph Cn,j of degree four with n vertices and chord length J, 2 ≤ J ≤ n, by computing its Lovász theta function θ(C n,j). 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. © Springer-Verlag 2004.",
issn = "0302-9743",
eissn = "1611-3349",
language = "eng",
}