Специальные структуры данных для задач на графах, связанных с понятием клики или с модульными декомпозициями

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 полезна для решения графовых задач, связанных с понятием клики и с различными типами декомпозиций, основанных на понятии модуля.