О.А. ЩЕРБИНА. Роль графовых структур в теории локальных элиминационных алгоритмов.

УДК 519.68

О.А. Щербина. Роль графовых структур в теории локальных элиминационных алгоритмов (русский) // Динамические системы: межвед. науч. сб. — ТНУ, 2008. — Вып 24. — С. 83–98.

Рассмотрено использование различных графовых структур в теории локальных элиминационных алгоритмов (ЛЭА) для решения дискретных задач, в том числе элиминационных графов и элиминационных деревьев. Показано, что бесконтурный орграф вычислительной процедуры ЛЭА является элиминационным деревом. Обсуждаются возможности построения древовидной декомпозиции на основе элиминационного дерева, а также представление элиминационного процесса с помощью множеств достижимости.

Ил. 1. Библиогр. 31 назв.

УДК 519.68

О.О. ЩЕРБИНА. Роль графових структур у теорiї локальних елiмiнацiйних алгоритмiв (росiйська) // Динамические системы: мiжвiд. наук. зб. — ТНУ, 2008. — Вип 24. — С. 83–98.

Розглянуто застосування рiзних графових структур у теорiї локальних елiмiнацiйних алгоритмiв (ЛЕА), в тому числi елiмiнацiйних графiв та елiмiнацiйних дерев. Показано, що безконтурний орграф обчислювальної процедури ЛЕА є елiмiнацiйним деревом. Обговорюються можливостi побудови деревовидної декомпозицiї на основi елiмiнацiйного дерева, а також представлення елiмiнацiйного процесу за допомогою множин досяжностi.

Ил. 1. Бiблiогр. 31 назв.

MSC 2000: 90C10, 90C39, 49M27

O.A. SHCHERBINA. The role of graph structures in the theory of local elimination algorithms (Russian). Din. Sist., Simferopol’ 24, 83–98 (2008).

In this paper we study various graph structures in the theory of local elimination algorithms (LEA), including elimination graphs and elimination trees. It is shown that the DAG of computational procedure of the LEA is the elimination tree. Possibilities of building tree decomposition from the elimination tree and presentation of elimination process by reachability sets are discussed.

Fig. 1. Ref. 31.