Перевод названия: Structural decomposition of graphs and its application for solving optimization problems on sparse graphs
Тип публикации: статья из журнала
Год издания: 2014
Ключевые слова: дерево декомпозиции, Treewidth, Sparse graph, Graph algorithms, Tree decomposition, atom graph, разреженный граф, алгоритмы на графах, древовидная ширина, атом графа
Аннотация: Формализовано понятие разреженного графа через числовой параметр, известный как древовидная ширина графа. Предложен декомпозиционный подход решения оптимизационных задач на разреженных графах. Этот подход реализует принцип «разделяй и властвуй» и основан на атомарном представлении входного графа. Показано, что атомарное представленПоказать полностьюие графа может быть построено за полиномиальное время. Приведены свойства атомов, определяющие границы применения предлагаемого подхода. Представлены результаты использования атомарного представления графа в решении двух оптимизационных задах: вычисление кратчайших путей и нахождение наибольшей клики графа. Время выполнения результирующих алгоритмов линейно зависит от числа вершин входного графа, что позволяет с их помощью обрабатывать разреженные графы большой размерности за реальное время. The concept of a sparse graph is formalized through a numeric parameter called the treewidth of the graph. This parameter characterizes the size of cliques and separators of the graph. Sparse graphs have small treewidth. A decomposition technique for solving optimization problems on sparse graphs is proposed. This technique implements the principle of "divide and rule" and is based on the atomic representation of the input graph. By an atom of a graph is meant a maximal connected subgraph having no a clique being a minimal separator. An algorithm that creates the atomic representation of the input graph is presented. It is shown that this algorithm for graph G = (V, E) builds the atomic representation in time O(|V| T), 2
Журнал: Прикладная дискретная математика. Приложение
Выпуск журнала: № 7
Номера страниц: 154-157
ISSN журнала: 2226308X
Место издания: Томск
Издатель: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Национальный исследовательский Томский государственный университет