Структурная декомпозиция графа и её применение для решения оптимизационных задач на разреженных графах

Формализовано понятие разреженного графа через числовой параметр, известный как древовидная ширина графа. Предложен декомпозиционный подход решения оптимизационных задач на разреженных графах. Этот подход реализует принцип “разделяй и властвуй” и основан на атомарном представлении входного графа. Показано, что атомарное представление графа может быть построено за полиномиальное время. Приведены свойства атомов, определяющие границы применения предлагаемого подхода. Представлены результаты использования атомарного представления графа в решении двух оптимизационных задах: вычисление кратчайших путей и нахождение наибольшей клики графа. Время выполнения результирующих алгоритмов линейно зависит от числа вершин входного графа, что позволяет с их помощью обрабатывать разреженные графы большой размерности за реальное время.