Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа
Предложен приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа. С помощью этого алгоритма улучшено известное рекордное значение мощности максимального независимого множества для одного из графов. Пропонується наближений алгоритм розв'язання задачі зн...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84596 |
| 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: | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа / И.П. Градинар // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 138-148. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| Summary: | Предложен приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа. С помощью этого алгоритма улучшено известное рекордное значение мощности максимального независимого множества для одного из графов.
Пропонується наближений алгоритм розв'язання задачі знаходження максимальної незалежної множини вершин графа. За допомогою цього алгоритму покращено відоме рекордне значення потужності максимальної незалежної множини для одного з графів.
In the paper, an approximate algorithm for solving the problem of finding a maximum independent set in a graph is proposed. With the help of this algorithm the known record value of cardinality of the maximum independent set is improved for one of the graphs.
|
|---|---|
| ISSN: | ХХХХ-0003 |