Applications of the inverse theta number in stable set problems

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

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

Letöltés (320kB)

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Konferencia neve: Symposium on Programming Languages and Software Tools, 13th, August 26-27, 2013, Szeged, Hungary
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Kötet/évfolyam: 21
Szám: 3
ISSN: 0324-721X
Nyelv: angol
DOI: 10.14232/actacyb.21.3.2014.12
Kulcsszavak: Informatika
Megjegyzések: Bibliogr.: 494. p. és a lábjegyzetekben
A feltöltés ideje: 2016. okt. 17. 10:37
Utolsó módosítás: 2018. jún. 05. 15:44
URI: http://acta.bibl.u-szeged.hu/id/eprint/34480
Bővebben:
Tétel nézet Tétel nézet