Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/14462
Title: | Специальные структуры данных для задач на графах, связанных с понятием клики или с модульными декомпозициями |
Authors: | Перез Чернов, Александр Хуанович Суздаль, С. В. |
Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
Issue Date: | Jan-2007 |
Publisher: | БГУ |
Citation: | Вестник Белорусского государственного университета. Сер. 1, Физика. Математика. Информатика. – 2007. - № 1. - С.103-108 |
Abstract: | We developed a new graph data structure S combining advantages of both the adjacency matrix and the adjacency lists. The data structure S is useful for solving graph problems related to the notion of clique and different kinds of decomposition based on the concept of module. Разработана новая графовая структура данных S, которая содержит преимущества как матрицы смежности, так и списков смежности. Структура данных строится по спискам смежности графа G за время 0(m+m), где n и m - число вершин и ребер графа соответственно. С помощью структуры S можно выполнять ряд операций. Предоставление NG(v)может быть выполнено за время O(degG v). Для определения смежности двух вершин графа требуется O(1) времени. Операция удаления вершины V может быть выполнена за время O(degG v). Предоставление NG(v) может быть выполнено за время O(degG v). Структура данных S полезна для решения графовых задач, связанных с понятием клики и с различными типами декомпозиций, основанных на понятии модуля. |
URI: | http://elib.bsu.by/handle/123456789/14462 |
ISSN: | 0321-0367 |
Licence: | info:eu-repo/semantics/openAccess |
Appears in Collections: | 2007, №1 (январь) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
103-108.pdf | 270,33 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.