|
Журнал вычислительной математики и математической физики, 1982, том 22, номер 6, страницы 1518–1521
(Mi zvmmf5638)
|
|
|
|
Научные сообщения
Об одном методе выделения бикомпонент в насыщенных орграфах
А. Р. Белкин Москва
Аннотация:
Рассматривается задача выделения всех бикомпонент ориентированного графа, число дуг в котором достаточно велико. Предлагается достроить исследуемый граф до полного и выделять бикомпоненты в полном орграфе, используя специальные показатели, содержащие необходимую информацию в агрегированном виде. Показано, что алгоритм, использующий данную идею, позволяет за $O(n^2)$ операций решить задачу или хотя бы осуществить ее декомпозицию, причем при наличии некоторой предварительной информации эта оценка может быть улучшена до $O(n)$.
Поступила в редакцию: 06.11.1980 Исправленный вариант: 19.02.1981
Образец цитирования:
А. Р. Белкин, “Об одном методе выделения бикомпонент в насыщенных орграфах”, Ж. вычисл. матем. и матем. физ., 22:6 (1982), 1518–1521; U.S.S.R. Comput. Math. Math. Phys., 22:6 (1982), 250–254
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/zvmmf5638 https://www.mathnet.ru/rus/zvmmf/v22/i6/p1518
|
Статистика просмотров: |
Страница аннотации: | 195 | PDF полного текста: | 105 | Первая страница: | 1 |
|