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...
Elmentve itt :
| Szerző: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
2014
|
| Sorozat: | Acta cybernetica
21 No. 3 |
| Kulcsszavak: | Számítástechnika |
| Tárgyszavak: | |
| doi: | 10.14232/actacyb.21.3.2014.12 |
| Online Access: | http://acta.bibl.u-szeged.hu/34480 |
| LEADER | 01308nab a2200241 i 4500 | ||
|---|---|---|---|
| 001 | acta34480 | ||
| 005 | 20220620092423.0 | ||
| 008 | 161017s2014 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 024 | 7 | |a 10.14232/actacyb.21.3.2014.12 |2 doi | |
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Ujvári Miklós | |
| 245 | 1 | 0 | |a Applications of the inverse theta number in stable set problems |h [elektronikus dokumentum] / |c Ujvári Miklós |
| 260 | |c 2014 | ||
| 300 | |a 481-494 | ||
| 490 | 0 | |a Acta cybernetica |v 21 No. 3 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika | ||
| 710 | |a Symposium on Programming Languages and Software Tools (2013) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/34480/1/actacyb_21_3_2014_12.pdf |z Dokumentum-elérés |