Applications of the inverse theta number in stable set problems

In the paper we introduce a semidefinite upper bound on the square of the stability number of a graph, the inverse theta number, which is proved to be multiplicative with respect to the strong graph product, hence to be an upper bound for the square of the Shannon capacity of the graph. We also desc...

Full description

Saved in:
Bibliographic Details
Main Author: Ujvári Miklós
Corporate Author: Symposium on Programming Languages and Software Tools (2013) (Szeged)
Format: Article
Published: 2014
Series:Acta cybernetica 21 No. 3
Kulcsszavak:Számítástechnika
Subjects:
doi:10.14232/actacyb.21.3.2014.12

Online Access:http://acta.bibl.u-szeged.hu/34480
Description
Summary:In the paper we introduce a semidefinite upper bound on the square of the stability number of a graph, the inverse theta number, which is proved to be multiplicative with respect to the strong graph product, hence to be an upper bound for the square of the Shannon capacity of the graph. We also describe a heuristic algorithm for the stable set problem based on semidefinite programming, Cholesky factorization, and eigenvector computation.
Physical Description:481-494
ISSN:0324-721X