Об одной верхней оценке для взвешенного числа устойчивости графа
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...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2007 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2007
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84998 |
|---|---|
| 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 |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Об одной верхней оценке для взвешенного числа устойчивости графа |
| spellingShingle |
Об одной верхней оценке для взвешенного числа устойчивости графа Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| title_short |
Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_full |
Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_fullStr |
Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_full_unstemmed |
Об одной верхней оценке для взвешенного числа устойчивости графа |
| title_sort |
об одной верхней оценке для взвешенного числа устойчивости графа |
| author |
Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| author_facet |
Стецюк, П.И. Бутенко, С.И. Березовский, О.А. |
| publishDate |
2007 |
| language |
Russian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
On one upper bound for the weighted stability number of a graph |
| 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.
|
| issn |
XXXX-0013 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84998 |
| citation_txt |
Об одной верхней оценке для взвешенного числа устойчивости графа / П.И. Стецюк, С.И. Бутенко, О.А. Березовский // Теорія оптимальних рішень: Зб. наук. пр. — 2007. — № 6. — С. 80-89. — Бібліогр.: 5 назв. — рос. |
| 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 |
| first_indexed |
2025-12-07T16:13:37Z |
| last_indexed |
2025-12-07T16:13:37Z |
| _version_ |
1850866681956532224 |