Главная страница
russian   english
16+
<< назад

Название статьи

О ГРАФОВОМ ТЕСТЕ ПРОВЕРКИ СМЕЖНОСТИ ЭКСТРЕМАЛЬНЫХ ЛУЧЕЙ МНОГОГРАННОГОКОНУСАВ МЕТОДЕ ДВОЙНОГО ОПИСАНИЯ


Номер журнала
6
Дата выпуска
2013

Тип статьи
научная статья
Коды УДК
519.6
Страницы
223-226
Ключевые слова
многогранный конус, метод двойного описания, алгоритм Моцкина–Бургера, графовый тест

Авторы
Золотых Н.Ю.

Место работы
Золотых Н.Ю.
Нижегородский госуниверситет им. Н.И. Лобачевского


Аннотация
Уточняется верхняя оценка сложности предложенного ранее графового теста проверки смежности экстремальных лучей в методе двойного описания.

Загрузить статью

Библиографический список
1 . Моцкин Т.С., Райфа Х., Томпсон Д.Л., Тролл Р.М. Метод двойного описания // Матричные игры. М.: Физматгиз, 1961.
2 . Черников С.Н. Линейные неравенства. М.: Наука, 1968.
3 . Шевченко В.Н., Груздев Д.В. Модификация алгоритма Фурье–Моцкина для построения триангуляций // Дискретный анализ и исследование операций. Сер. 2. 2003. Т. 10. № 1. С. 53–64.
4 . Золотых Н.Ю. Новая модификация метода двойного описания для построения остова многогранного конуса // Журнал вычислительной математики и математической физики. 2012. Т. 52. № 1. С. 153–163.
5 . Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. М.: Мир, 1991.
6 . Fukuda K., Prodon A. Double description method revisited // Combinatorics and Computer Science. Springer-Verlag, 1996. P. 91–111.
7 . Avis D., Bremner D., Seidel R. How good are convex hull algorithms? // Computational Geometry: Theory and Apllications. 1997. V. 7. № 5–6. P. 265–301.
8 . Burger E. ?ngleichungssysteme // Zeitschrift f?r Angewandte Mathematik und Mechanik. 1956. V. 36. № 3/4. P. 135–139.
9 . Черникова Н.В. Алгоритм для нахождения общей формулы неотрицательных решений системы линейных уравнений // Журнал вычислительной математики и математической физики. 1964. Т. 4. № 4. С. 733–738.
10 . Веселов С.И., Парубочий И.Е., Шевченко В.Н. Программа нахождения остова конуса неотрицательных решений системы линейных неравенств // Системные и прикладные программы. Часть 2. Горький: Изд-во Горьк. ун-та, 1984. С. 83–92.
11 . Le Verge H. A note on Сhernikova's algorithm: Research Report RR–1662. Rennes: INRIA, 1992.
12 . Золотых Н.Ю., Лялин С.С. Параллельный алгоритм нахождения общего решения системы линейных неравенств // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. № 5. С 193–199.
13 . Бастраков С.И., Золотых Н.Ю. Использование идей алгоритма Quickhull в методе двойного описания // Вычислительные методы и программирование. 2011. Т. 12. № 1. С. 232–237.