Optimization problem for star covers of graphs without four cycles
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910229022638080 |
|---|---|
| author | Bukovšek, Damjana Kokol Oblak, Polona Šmigoc, Helena |
| author_facet | Bukovšek, Damjana Kokol Oblak, Polona Šmigoc, Helena |
| contents | This work presents a study of star covers on graphs. Unlike traditional formulations that minimize the number of stars, our aim is to optimize the number of bipartite components used in the cover. This problem, motivated by a symmetric nonnegative trifactorization of matrices and the SNT-rank of graphs, is in general hard to solve. We consider a family of graphs that do not contain four cycles, and develop an algorithm to determine the SNT-rank of such graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_17383 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Optimization problem for star covers of graphs without four cycles Bukovšek, Damjana Kokol Oblak, Polona Šmigoc, Helena Combinatorics Rings and Algebras 05C35, 05C50, 15A23 This work presents a study of star covers on graphs. Unlike traditional formulations that minimize the number of stars, our aim is to optimize the number of bipartite components used in the cover. This problem, motivated by a symmetric nonnegative trifactorization of matrices and the SNT-rank of graphs, is in general hard to solve. We consider a family of graphs that do not contain four cycles, and develop an algorithm to determine the SNT-rank of such graphs. |
| title | Optimization problem for star covers of graphs without four cycles |
| topic | Combinatorics Rings and Algebras 05C35, 05C50, 15A23 |
| url | https://arxiv.org/abs/2605.17383 |