О ГРАФОВОМ ТЕСТЕ ПРОВЕРКИ СМЕЖНОСТИ ЭКСТРЕМАЛЬНЫХ ЛУЧЕЙ МНОГОГРАННОГОКОНУСАВ МЕТОДЕ ДВОЙНОГО ОПИСАНИЯ |
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. |