Applications of the inverse theta number in stable set problems

Ujvári Miklós: Applications of the inverse theta number in stable set problems. In: Acta cybernetica, (21) 3. pp. 481-494. (2014)

[thumbnail of actacyb_21_3_2014_12.pdf]
Cikk, tanulmány, mű

Download (320kB) | Preview


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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2014
Volume: 21
Number: 3
ISSN: 0324-721X
Page Range: pp. 481-494
Language: English
Place of Publication: Szeged
Event Title: Symposium on Programming Languages and Software Tools (2013) (Szeged)
Related URLs:
DOI: 10.14232/actacyb.21.3.2014.12
Uncontrolled Keywords: Számítástechnika
Additional Information: Bibliogr.: 494. p. és a lábjegyzetekben ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 17. 10:37
Last Modified: 2022. Jun. 20. 09:24

Actions (login required)

View Item View Item