文章基本信息

标题：Computation of the Lov\'asz Theta Function for Circulant Graphs
本地全文：下载
作者：Valentin E. Brimkov ; Bruno Codenotti ; Valentino Crespi 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The Lov\'asz theta function ( G ) of a graph G has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique and chromatic number, two well known hard to compute quantities. In this paper we deal with the computation of the Lov\'asz function of certain circulant graphs, i.e., graphs whose adjacency matrix is circulant. Such graphs are important for both theoretical and practical reasons, and indeed arise in many different contests. The simplest circulant graph is the cycle; for the cycle, Lov\'asz showed a simple formula expressing the value of the theta function. We consider the theta function of circulant graphs which can be viewed as the super-position of two cycles, i.e., circulant graphs of degree 4. We invertigate the possibility to take advantage of the specifis structure of the circulants in oreder to achieve higher efficiency. For a circulant graph C n j on n vertices and with a chord length j , 2 j n 2 , we propose an O ( j ) time algorithm to compute ( C n j ) if j is odd and an O ( n j ) time algorithm if j is even. This is a significant improvement over the best known algorithms for the theta function computation for general graphs which take O ( n 4 ) time. We also derive conditions under which ( C n j ) can be computed in O (1) time.
关键词：circulant graph , linear programming , Lov\'asz theta-function , time complexity of algorithm