Об одной верхней оценке для взвешенного числа устойчивости графа
We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on th...
Gespeichert in:
| Veröffentlicht in: | Теорія оптимальних рішень |
|---|---|
| Datum: | 2007 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862690473203728384 |
|---|---|
| author | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| author_facet | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| citation_txt | Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on the polytope CSTAB(G) , and it is also an exact upper bound for the weighted stability number of the t-perfect graph.
|
| first_indexed | 2025-12-07T16:13:37Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-84998 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T16:13:37Z |
| publishDate | 2007 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.И. Бутенко, С.И. Березовский, О.А. 2015-07-18T06:16:34Z 2015-07-18T06:16:34Z 2007 Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84998 519.8 We derived an upper bound for the weighted stability number of a simple undirected graph G, which is the solution of a linear pogramming problem with O(|V|³) constraints, where V is a number of vertices in the graph. We proved that this upper bound is at least as good as the known bound based on the polytope CSTAB(G) , and it is also an exact upper bound for the weighted stability number of the t-perfect graph. Работа выполнена при финансовой поддержке гранта UKM2-2812-KV-06 (CRDF Cooperative Grants Programm). ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Об одной верхней оценке для взвешенного числа устойчивости графа On one upper bound for the weighted stability number of a graph Article published earlier |
| spellingShingle | Об одной верхней оценке для взвешенного числа устойчивости графа Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| title | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_alt | On one upper bound for the weighted stability number of a graph |
| title_full | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_fullStr | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_full_unstemmed | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_short | Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_sort | об одной верхней оценке для взвешенного числа устойчивости графа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| work_keys_str_mv | AT stecûkpi obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT butenkosi obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT berezovskiioa obodnoiverhneiocenkedlâvzvešennogočislaustoičivostigrafa AT stecûkpi ononeupperboundfortheweightedstabilitynumberofagraph AT butenkosi ononeupperboundfortheweightedstabilitynumberofagraph AT berezovskiioa ononeupperboundfortheweightedstabilitynumberofagraph |