Метод перечисления максимальных независимых множеств в неориентированных графах

На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125....

Full description

Saved in:

Bibliographic Details
Published in:	Электронное моделирование
Date:	2017
Main Authors:	Листровой, С.В., Сидоренко, А.В., Листровая, Е.С.
Format:	Article
Language:	Russian
Published:	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2017
Subjects:	Математическое моделирование и вычислительные методы
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/127632
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:	Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-127632
record_format	dspace
spelling	Листровой, С.В. Сидоренко, А.В. Листровая, Е.С. 2017-12-24T11:14:28Z 2017-12-24T11:14:28Z 2017 Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/127632 519.682.1 На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125. На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125. Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Метод перечисления максимальных независимых множеств в неориентированных графах Method of enumeration of maximum independent sets in nonoriented graphs 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	Листровой, С.В. Сидоренко, А.В. Листровая, Е.С.
topic	Математическое моделирование и вычислительные методы
topic_facet	Математическое моделирование и вычислительные методы
publishDate	2017
language	Russian
container_title	Электронное моделирование
publisher	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
format	Article
title_alt	Method of enumeration of maximum independent sets in nonoriented graphs
description	На основе рангового подхода предложен метод перечисления максимальных независимых множеств неориентированного связного графа с временной сложностью, в среднем не превышающей O (n⁶), где n — число вершин в графе, для графов, не содержащих разделяющих вершин, размерность которых не превышает n = 125. На основі рангового підходу запропоновано метод перерахування максимальних незалежних множин неорієнтованого зв’язного графа з часовою складністю, що в середньому не перевищує O (n⁶), де n — число вершин у графі, для графів, що не мають розділяючих вершин, розмір яких не перевищує n = 125. Based on the rank approach the authors propose a method of enumeration of maximum independent sets of nonoriented connected graph with time complexity that does not exceed, at an average, O (n⁶), where n is the number of vertices in the graph, for the graphs which do not contain separating vertices, which dimension does not exceed n=125.
issn	0204-3572
url	https://nasplib.isofts.kiev.ua/handle/123456789/127632
citation_txt	Метод перечисления максимальных независимых множеств в неориентированных графах / С.В. Листровой, А.В. Сидоренко, Е.С. Листровая // Электронное моделирование. — 2017. — Т. 39, № 4. — С. 3-17. — Бібліогр.: 12 назв. — рос.
work_keys_str_mv	AT listrovoisv metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT sidorenkoav metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovaâes metodperečisleniâmaksimalʹnyhnezavisimyhmnožestvvneorientirovannyhgrafah AT listrovoisv methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT sidorenkoav methodofenumerationofmaximumindependentsetsinnonorientedgraphs AT listrovaâes methodofenumerationofmaximumindependentsetsinnonorientedgraphs
first_indexed	2025-12-07T13:29:37Z
last_indexed	2025-12-07T13:29:37Z
_version_	1850856363659362304

Метод перечисления максимальных независимых множеств в неориентированных графах

Institution

Similar Items