Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа
Предложен приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа. С помощью этого алгоритма улучшено известное рекордное значение мощности максимального независимого множества для одного из графов. Пропонується наближений алгоритм розв'язання задачі зн...
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| _version_ | 1860058587936587776 |
|---|---|
| author | Градинар, И.П. |
| author_facet | Градинар, И.П. |
| citation_txt | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа / И.П. Градинар // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 138-148. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Предложен приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа. С помощью этого алгоритма улучшено известное рекордное значение мощности максимального независимого множества для одного из графов.
Пропонується наближений алгоритм розв'язання задачі знаходження максимальної незалежної множини вершин графа. За допомогою цього алгоритму покращено відоме рекордне значення потужності максимальної незалежної множини для одного з графів.
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.
|
| first_indexed | 2025-12-07T17:03:15Z |
| format | Article |
| fulltext |
138 К омпьютерная математика. 2010, № 2
Òåîðèÿ è ìåòîäû
îïòèìèçàöèè
Предложен приближенный алго-
ритм решения задачи нахождения
максимального независимого мно-
жества вершин графа. С помо-
щью этого алгоритма улучшено
известное рекордное значение
мощности максимального незави-
симого множества для одного из
графов.
И.П. Градинар, 2010
ÓÄÊ 519.854
È.Ï. ÃÐÀÄÈÍÀÐ
ÏÐÈÁËÈÆÅÍÍÛÉ ÀËÃÎÐÈÒÌ
ÐÅØÅÍÈß ÇÀÄÀ×È ÍÀÕÎÆÄÅÍÈß
ÌÀÊÑÈÌÀËÜÍÎÃÎ ÍÅÇÀÂÈÑÈÌÎÃÎ
ÌÍÎÆÅÑÒÂÀ ÂÅÐØÈÍ ÃÐÀÔÀ
Введение. Известно, что задача нахождения
максимального независимого множества
вершин графа имеет многочисленные прак-
тические приложения [1–3]. Для ее решения
в данной работе предложен и исследован
приближенный алгоритм. Использование
этого алгоритма позволило найти известные
из литературы рекордные значения мощно-
сти независимого множества, а для одного
графа улучшить его.
Постановка задачи. Пусть задан неориен-
тированный граф = ( , )G V E , где =V
1= { , , }kv v… – множество его вершин,
1= { , , }mE e e… – множество ребер ( | |k V= ,
| |m E= ), | |V – мощность множества V.
Приведем необходимые определения.
Множество I V⊂ вершин графа G называ-
ется независимым, если никакие две его
вершины не связаны ребром, т. е.
1 2 1 2= { | , , = ( , ) }.I v V v v I e v v E∈ ∀ ∈ ∃ ∈
Независимое множество maxI называется
максимальным независимым множеством,
если для любого независимого множества I
выполняется соотношение | | | |maxI I≥ . Обо-
значим ( )Gα число элементов в maxI , т. е.
( ) =| |maxG Iα . Независимое множество I
называется максимальным по включению,
если оно не является подмножеством неко-
торого другого независимого множества.
Известно [1], что задача отыскания макси-
мального независимого множества вершин
графа сводится к задаче целочисленного про-
граммирования с булевыми переменными
вида
ПРИБЛИЖЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО …
Компьютерная математика. 2010, № 2 139
1 :( , )
max ( ) (1 ) :
i j
k
k
i j
i j v v E
f x x x x B
= ∈
= − ∈
∑ ∏ ,
где каждой вершине jv V∈ графа = ( , )G V E ставится в соответствие перемен-
ная {0,1}, = 1, ,jx j k∈ … .
Пусть
( ) = { | =1, =1, , }j jI x v V x j k∈ … , где 1= ( , , ).kx x x…
Если выполняется условие ( ) =| ( ) |f x I x , то ( )I x – независимое множество вер-
шин графа = ( , )G V E .
Поскольку рассматриваемая задача – NP -трудная [1], то актуальным явля-
ется вопрос разработки приближенных алгоритмов ее решения. На сегодняшний
день известен ряд алгоритмов [1, 2, 4–7] для этой задачи. Среди них алгоритмы,
использующие локальный поиск: вектора спада, табу, глобального равновесного
поиска и др. Каждый из них имеет свои особенности и преимущества при при-
менении к поставленной задаче. Обзор некоторых приближенных алгоритмов
решения данной задачи приведен в [3].
Описание предлагаемого алгоритма. Пусть ( )GN v – множество вершин
неориентированного графа = ( , )G V E , инцидентных вершине v V∈ , т. е.
( ) = { | = ( , ) },GN v u V e u v E∈ ∃ ∈
и пусть для V V′ ⊂
( ) = ( ).G G
v V
N V N v
′∀ ∈
′ ∪
Обозначим ( )Gdeg v степень вершины v (количество вершин, инцидентных
вершине v ), т.е. ( ) =| ( ) |G Gdeg v N v . Пусть ( )Gδ – число, равное наименьшей
степени вершин графа = ( , )G V E , т.е. ( ) = min{ ( ) | }.GG deg v v Vδ ∀ ∈
Предположим, что [ ] = ( , ( ))G V V E V V′ ′ ′ ′∩ × – подграф графа = ( , )G V E ,
порожденный подмножеством V V′ ⊂ .
Предлагаемый в данной работе алгоритм заключается в следующем.
Если v принадлежит независимому множеству I , то никакая вершина
из ( )GN v не может быть включена в множество I . Множество вершин, кото-
рые не могут быть включены в I , обозначим T , т.е. = ( ).GT N I
При формировании множества I есть вершины, не принадлежащие множе-
ству T , и еще не включенные в I , т.е. они не связаны в графе G ни с одной
вершиной из множества I и есть претендентами на включение в независимое
множество. Множество таких вершин обозначим
= \ \ ( )GA V I N I или = { | ; , = ( , ) }.A v V v I u I e v u E∈ ∈ ∀ ∈ ∃ ∈/
И.П. ГРАДИНАР
Компьютерная математика. 2010, № 2 140
Множества I , A и T определены таким образом, что они являются разбие-
ниями множества V , т.е. =V I A T∪ ∪ , а их попарное пересечение равняется
пустому множеству. Таким образом, каждая вершина графа G обязательно
должна принадлежать только одному из этих трех множеств.
В зависимости от того, к какому из множеств I , A или T принадлежит
вершина v V∈ , вершины v′ из окрестности ( )GN v могут принадлежать таким
множествам:
1) , ( ),Gv I v N v v T′ ′∀ ∈ ∀ ∈ ∈ ;
2) , ( ), ( ) ( )Gv A v N v v A v T′ ′ ′∀ ∈ ∀ ∈ ∈ ∨ ∈ ;
3) , ( ), ( ) ( )Gv T v N v v A v T′ ′ ′∀ ∈ ∀ ∈ ∈ ∨ ∈ .
Очевидно, что если =A V , то =I ∅ , =T ∅ . Если же =A ∅ , то это значит,
что I – максимальное по включению независимое множество, возможно (но не
обязательно), максимальное независимое множество.
При включении в I некоторой вершины v , а это возможно, когда она при-
надлежит A , из последнего множества она удаляется. Те вершины из окрестно-
сти ( )GN v , которые принадлежат множеству A (т.е. ( )GN v A∩ или [ ]( )G AN v ),
переходят в множество T . Другие вершины не изменяют своего “статуса”.
Схематично это выглядит следующим образом:
( )Gv N v AI A T∩← → .
При удалении из I определенной вершины v она автоматически переходит
в множество A . Вершины из окрестности ( )GN v (все они принадлежат T при
v I∈ ), которые не имеют связей ни с одной из вершин из I , кроме v , переходят
в множество A . Другие вершины не изменяют своей принадлежности к одному
из соответствующих множеств I , A или T . Схематично это имеет вид
( )\ ( \ ) .G GN v N I vvI A T→ ←
Предположим, что рассмотренные особенности включения в I и удаления
из I вершины v с соответствующими последствиями для окрестности ( )GN v
полностью реализовываются следующими базовыми процедурами:
procedure включение_в_ I _вершины (номер_вершины_из_ A )
v ← A [номер_вершины_из_ A ]
удаление из A вершины v и включение ее в множество I
удаление из A вершин, принадлежащих ( )GN v , и включение их в T .
procedure удаление_из_ I _вершины (номер_вершины_из_ I )
v ← I [номер_вершины_из_ I ]
удаление из I вершины v и включение ее в множество A
удаление из T вершин ' ( )\ ( \ )G Gv N v N I v∈ и включение их в A .
ПРИБЛИЖЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО …
Компьютерная математика. 2010, № 2 141
В дальнейшем будем считать, что доступ к множествам ,I A и T для вне-
сения изменений осуществляется только с помощью этих двух процедур.
Без этих процедур возможно лишь считывание информации о состоянии этих
множеств, а именно об их мощности и содержимом.
Обозначим [ ]= { | ( ) = ( [ ])}G AA v A deg v G Aδ ∈ δ подмножество множества
вершин A , имеющих наименьшую степень ( [ ])G Aδ в графе [ ]G A . С помощью
следующей процедуры постепенно и рандомизированно удаляются из множест-
ва A вершины, принадлежащие A Aδ ⊂ , они затем включаются в I . Это проис-
ходит до тех пор, пока множество A не станет пустым.
procedure рандомизированное_включение_в_ I _вершин_из_ ()δA
while A≠∅ do
включение_в_ I _вершины(номер в A вершины δA [random(| δA |)])
Приведем процедуру, которая рандомизированно удаляет из I определен-
ное количество вершин.
procedure рандомизированное_удаление_из_ I _вершин (кол-во_на_удаление)
j :=0, количество_на_удаление:=min{ кол-во_на_удаление, | I |}
while j < количество_на_удаление do
удаление_из_ I _вершины(random(| I |))
j := j +1
Вышеописанные базовые процедуры будут использованы далее. Схему
предложенного приближенного алгоритма представим в виде таких процедур:
procedure начальная_настройка (выделенное_время)
конец:=false
время_окончания_работы_алгоритма:=now+ выделенное _время
количество_стартов:=0
procedure новое_начальное_решение ()
:I = ∅ , :A V= , :T = ∅
рандомизированное_включение_в_ I _вершин_из_ δA ()
количество_стартов:=количество_стартов+1
средняя_начальная_мощность_ I := (средняя_начальная_мощность_ I ·
·(количество_стартов–1)+| I | ) / количество_стартов
увеличилась_мощность_ I ()
_i max :=random([|V |*0.03])+[|V |*0.001]+1
И.П. ГРАДИНАР
Компьютерная математика. 2010, № 2 142
procedure увеличилась_мощность_ I ()
наибольшая_мощность_ I :=| I |
граница_спада_мощности_ I := | I | – 20
_i del :=1
i :=0
procedure приближенный_алгоритм(выделенное_время, ожидаемый_результат)
начальная_настройка(выделенное_время), количество_стартов:=0
while (not конец) do
новое_начальное_решение()
if | I |≥ожидаемый_результат then конец:=true
while (| I |> средняя_начальная_мощность_I)and
and ( _i del <2/3·| I |)and(not конец) do
while ( i < _maxi )and(not конец) do
рандомизированное_удаление_из_ I _вершин( _i del )
рандомизированное_включение_в_ I _вершин_из_ δA ()
if наибольшая_мощность_ I <| I | then
увеличилась_мощность_ I ()
if | I |≥ожидаемый_результат then конец:=true
i := i +1
_i del := _i del +1
i :=0
if | I |< граница_спада_мощности_ I then
_i del :=1
граница_спада_мощности_ I := граница_спада_мощности_ I – 20
if now<время_окончания_работы_алгоритма then конец:=true
Суть алгоритма заключается в попытке заменить в текущем множестве I
_i del вершин большим количеством вершин и тем самым увеличить мощность
этого множества. Благодаря рандомизированному выбору среди вершин наи-
меньшей степени, которые появились в множестве A после удаления _i del вер-
шин из множества I , мощность I не уменьшается или существенно не умень-
шается. Но когда за количество шагов _maxi не увеличивается мощность I , не-
обходимо увеличить _i del . Если увеличивается | |I , то _i del принимает значе-
ние 1, и снова формируем множество I большей мощности при малых значени-
ях _i del . Когда _i del довольно большое, то возможно существенное уменьше-
ние мощности независимого множества и нет смысла дальше продолжать поиск.
ПРИБЛИЖЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО …
Компьютерная математика. 2010, № 2 143
В таком случае поиск необходимо завершить и продолжить работу алгоритма с
нового начального решения. В процессе работы алгоритма не сохраняются неза-
висимые множества для дальнейшего использования, кроме текущего и наи-
большего независимых множеств, т. е. алгоритм не нуждается в большом объеме
памяти.
Результаты экспериментальных расчетов. Данный алгоритм был приме-
нен для ряда графов. Программная реализация предложенного алгоритма бы-
ла скомпилирована с помощью Borland Delphi 5.0 (build 5.62) и запущена на
компьютере с конфигурацией Intel® Core™2 CPU, T7200 @ 2.00GHz, 2GB RAM
при загрузке 50 %. Каждая задача решалась 10 раз с ограничением по времени
в 5 часов. Полученные результаты представлены в таблице. В колонке 5 этой
таблицы приведено среднее время получения наибольшей мощности независи-
мого множества по десяти запускам, в колонке 6 среднеквадратичное отклоне-
ние времени получения наибольшей мощности. В колонке 7 приведены из [2]
полученные результаты нахождения максимального независимого множества и
затраченное на них время (« – » означает, что граф не рассматривался, «*» – что
рекорд не достигнут).
Из результатов, приведенных в таблице, видно, что получены известные ре-
кордные значения [1, 4, 5, 8] мощности независимого множества для всех гра-
фов. Кроме графа 1 8192zc , рекордные значения найдены в результате всех
10 запусков алгоритма. Для графа 1 8192zc с помощью предложенного алгорит-
ма улучшено известное [1, 6] рекордное значение от значения 701 до 704 . Зна-
чение 704 для этого графа получено в результате 9 из 10 решений задачи, при
одном решении получено 703 . При разработке алгоритма, который предлагает-
ся в данной работе, внимание было нацелено на 1zc -графы, для одного из кото-
рых и улучшено известное рекордное значение. Для оценки эффективности ал-
горитма поставленная задача была решена и для DIMACS-графов. Сравнив ре-
зультат нахождения рекордов по этим графам с результатами, полученными ал-
горитмом VSA в работе [2] (таблица), можно сказать, что предложенный алго-
ритм проявляет приемлемую эффективность и для других графов.
Графики (рис. 1–5) схематично иллюстрируют работу предложенного алго-
ритма. На них отображены:
1) моменты увеличения _i del (рис. 1–3);
2) изменение | |I в зависимости от значения _i del (рис. 2–5);
3) момент, когда | |I увеличивается, а _i del принимает значение 1 (рис. 2, 3);
4) случаи нерационального увеличения _i del или сильного спада мощно-
сти I , когда процесс поиска начинается из нового решения (рис. 4, 5);
5) спад | |I к значению граница_спада_мощности_ I , когда _i del присваи-
вается 1, а переменной граница_спада_мощности_ I присваивается меньшее
значение (рис. 5).
И.П. ГРАДИНАР
Компьютерная математика. 2010, № 2 144
ТАБЛИЦА. Результаты вычислительных экспериментов
Название
графа
Известное
рекордное
значение
мощности
Полученное
наилучшее
значение
мощности
Среднее
значение
мощно-
сти
Среднее
время,
с
Отклоне-
ние,
с
Результат
и
время
в [2], с
1 2 3 4 5 6 7
keller4.clq 11 11 11 0,000 0,000 11, <1
johnson8-4-4.clq 14 14 14 0,000 0,000 14, <1
hamming8-4.clq 16 16 16 0,000 0,000 16, 2
san200_0.7_2.clq 18 18 18 1,381 1,242 18, <1
hamming10-4.clq 40 40 40 0,191 0,161 40, 23
MANN_a27.clq 126 126 126 0,014 0,009 125, *
hamming8-2.clq 128 128 128 0, 000 0,000 128, 3
hamming10-2.clq 512 512 512 0,002 0,005 512, 9
MANN_a45.clq 345 345 345 1118,198 555,325 343 , *
1zc1024 112 112 112 193,908 182,502 – , –
1zc2048 198 198 198 507,191 320,477 – , –
1zc4096 379 379 379 1880,859 1896,986 – , –
1zc8192 701 704 703,9 9977,937 7098,894 – , –
РИС. 1
ПРИБЛИЖЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО …
Компьютерная математика. 2010, № 2 145
РИС. 2
РИС. 3
И.П. ГРАДИНАР
Компьютерная математика. 2010, № 2 146
РИС. 4
РИС. 5
ПРИБЛИЖЕННЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ НАХОЖДЕНИЯ МАКСИМАЛЬНОГО …
Компьютерная математика. 2010, № 2 147
Заключение. Результаты проведенных вычислительных экспериментов по-
казали, что с помощью предлагаемого алгоритма для каждого графа получены
известные рекордные значения мощности независимого множества. Кроме того,
для графа 1 8192zc улучшено рекордное значение мощности независимого
множества.
І.П. Градинар
НАБЛИЖЕНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ЗНАХОДЖЕННЯ
МАКСИМАЛЬНОЇ НЕЗАЛЕЖНОЇ МНОЖИНИ ВЕРШИН ГРАФА
Пропонується наближений алгоритм розв'язання задачі знаходження максимальної
незалежної множини вершин графа. За допомогою цього алгоритму покращено відоме
рекордне значення потужності максимальної незалежної множини для одного з графів.
I.P. Gradinar
AN APPROXIMATE ALGORITHM FOR SOLVING THE PROBLEM OF MAXIMUM
INDEPENDENT SET IN A GRAPH
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.
1. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения,
исследования. – Киев: Наук. думка, 2003. – 264 с.
2. Balaji S., Swaminathan V., Kannan K. A Simple Algorithm to Optimize Maximum Independent
Set // Advanced Modeling and Optimization. – 2010. – 12. – P. 107–118.
(http://camo.ici.ro/journal/vol12/v12a9.pdf)
3. Градинар І. П. Наближені алгоритми знаходження перешкодозахищених кодів, що коре-
гують одну помилку в Z-каналі // Наук. вісн. Ужгород. ун-ту. Сер. математика і інфор-
матика. – 2009. – Вип. 18. − С. 20–30.
4. Сергиенко И.В., Шило В.П., Стецюк П.И. Приближенный алгоритм решения задачи на-
хождения максимального независимого множества // Компьютерная математика. – Киев:
Ин-т кибернетики им. В.М. Глушкова НАН Украины, 2000. – C. 4–20.
5. Andrade D., Resende M.G.C., Werneck R. Fast local search for the maximum independent set
problem // Proceedings of 7th Workshop on Experimental Algorithms (WEA 2008),
C.C. McGeoch (Ed.), LNCS. – 2008 – 5038. – P. 220–234.
(http://www2.research.att.com/~mgcr/doc/ls-indepset.pdf)
И.П. ГРАДИНАР
Компьютерная математика. 2010, № 2 148
6. Сергиенко И.В., Шило В.П. Проблемы дискретной оптимизации: сложные задачи,
основные подходы к их решению // Кибернетика и систем. анализ. – 2006. – № 4. –
С. 3–25.
7. Butenko S., Pardalos P.M., Sergienko I.V., Shylo V. and Stetsyuk P. Finding maximum inde-
pendent sets in graphs arising from coding theory // Symposium on Applied Computing,
Madrid, Spain, ACM Press. – 2002. – P. 542–546.
8. Sloane N. J. A. Challenge problems: Independent sets in graphs, 2000. Last update
Nov 18 2009.
http://www.research.att.com/~njas/doc/graphs.html
Получено 29.04.2010
Îá àâòîðå:
Градинар Иван Петрович,
аспирант Ужгородского национального университета.
e-mail: vgradinar@gmail.com
|
| id | nasplib_isofts_kiev_ua-123456789-84596 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T17:03:15Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Градинар, И.П. 2015-07-10T17:44:20Z 2015-07-10T17:44:20Z 2010 Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа / И.П. Градинар // Компьютерная математика: сб. науч. тр. — 2010. — № 2. — С. 138-148. — Бібліогр.: 8 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84596 519.854 Предложен приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа. С помощью этого алгоритма улучшено известное рекордное значение мощности максимального независимого множества для одного из графов. Пропонується наближений алгоритм розв'язання задачі знаходження максимальної незалежної множини вершин графа. За допомогою цього алгоритму покращено відоме рекордне значення потужності максимальної незалежної множини для одного з графів. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа Наближений алгоритм розв’язання задачі знаходження максимальної незалежної множини вершин графа An approximate algorithm for solving the problem of maximum independent set in a graph Article published earlier |
| spellingShingle | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа Градинар, И.П. Теория и методы оптимизации |
| title | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| title_alt | Наближений алгоритм розв’язання задачі знаходження максимальної незалежної множини вершин графа An approximate algorithm for solving the problem of maximum independent set in a graph |
| title_full | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| title_fullStr | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| title_full_unstemmed | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| title_short | Приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| title_sort | приближенный алгоритм решения задачи нахождения максимального независимого множества вершин графа |
| topic | Теория и методы оптимизации |
| topic_facet | Теория и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84596 |
| work_keys_str_mv | AT gradinarip približennyialgoritmrešeniâzadačinahoždeniâmaksimalʹnogonezavisimogomnožestvaveršingrafa AT gradinarip nabliženiialgoritmrozvâzannâzadačíznahodžennâmaksimalʹnoínezaležnoímnožiniveršingrafa AT gradinarip anapproximatealgorithmforsolvingtheproblemofmaximumindependentsetinagraph |