Аннотация

Для различных NP-полных задач разработаны эффективные эвристические алгоритмы. К сожалению, такие алгоритмы решают только некоторое подмножество индивидуальных задач. Примером такого алгоритма может служить алгоритм MIN для нахождения наибольшего независимого множества вершин графа. Теоретическая оценка сложности этого алгоритма равна O(n²). Однако, ошибка в решении может быть произвольно большой.

В данной работе мы исследуем возможность разработки эвристического алгоритма для задачи ВЫП, имеющего низкую временную оценку сложности. Идея построения такого алгоритма основывается на представлении задачи ВЫП как задачи покрытия.

Для поиска решения задачи мы используем метод, названный слепым. Рассмотрены два возможных подхода к реализации этого метода.

Один из них основан на представлении каждого литерала в каждом дизъюнкте как вершины ориентированного графа. Таким образом, такой граф может иметь m×n вершин, где m - число дизъюнктов, n - число булевых переменных. Теоретическая оценка сложности такого алгоритма равна O(N³ m), где O(N³ m), где N (N <= mn) - общее число литералов во всех дизъюнктах булевой функции.

Другой подход предполагает, что ориентированный граф может содержать 2n вершин, т.е. каждая вершина такого графа поиска соответствует одному из 2n возможных литералов. Теоретическая оценка сложности алгоритма, основанного на таком подходе равна O(m²n³).

Аннотация

Мы исследуем задачу о нахождении наибольшего независимого множества вершин в неориентированном графе. Главный результат состоит в том, что эта задача может рассматриваться как решение этой же проблемы в подклассе взвешенных нормальных парно-ортогональных графов. Сформулирована задача, двойственная к исходной. Показано, что для тривиальных парно-ортогональных графов любое максимальное независимое множество является наибольшим.

Статья опубликована в журнале "Кибернетика", N 1, 1989, с. 119-121.

Аннотация

Цель этой статьи - уточнить понятие класса задач NP.

Мы строим математическую модель дискретных проблем как систему независимости со взвешенными элементами. Мы вводим два вспомогательных множества, которые характеризуют решение задачи: присоединенное множество, которое содержит элементы из исходного множества, никакие из которых не могут быть присоединены к уже выбранным элементам решения; и остаточное множество, в котором каждый элемент может быть присоединен к ранее выбранным элементам решенияы.

В задаче без предвидения, каждое присоединенное множество может быть порожден решающим алгоритмом эффективно, за полиномиальное время.

Главный результат исследования - утверждение, что класс NP идентичен классу проблем без предвидения. Отсюда следует, что если мы желаем построить эффективный (полиномиально-временной) решающий алгоритм для некоторой задачи, то нам необходимо найти альтернативную формулировку задачи в множестве задач без предвидения.

Статья опубликована в журнале "Кибернетика и системный анализ", N 5, 1997, с. 30 - 36.

Аннотация

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

Статья опубликована в журнале "Надежные вычисления" (Reliable Computing), N 4, 1998, с. 119-202 (на русском и английском языках).

Аннотация

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

Английский вариант статьи опубликован в журнале "International Journal of Mathematics and Mathematical Sciences"", Vol. 26, issue 11, 2001. pp.679-684.
Hindawi Publishing Corporation.