Две квадратичные задачи для построения оценок и поиска максимальной клики
| Авторы: | А. А. Кузнецова |
| Аннотация: | Рассматривается задача поиска максимальной клики и ее сведение к двум непрерывным задачам. На основе непрерывного представления удается получить верхние оценки для размерности максимальной клики. Показано, в каких пределах должен варьироваться параметр, чтобы по решению непрерывной задачи можно было найти максимальную клику. |
| Ключевые слова: | задача о максимальной клике, верхние оценки |
| УДК: | 519.6 |
| Литература: |
1. Васильев Ф.П. Численные методы решения экстремальных задач. — М.: Наука, 1988. 2. Кузнецова А.А., Карпачева О.Н. Два метода локального поиска с параметрами для задачи о максимальной клике // Методы оптимизации и их приложения.: Тр. Междунар. конф. — Иркутск: ИСЭМ СО РАН, 2005. — Т. 1. — С. 527–533. 3. Bomze I. Evolution towards the maximum clique // J. of Global Optimization. — 1997. — V. 10. — P. 143–164. 4. Bomze I.M., Budinich M., Pardalos P.M., Pelillo, M. The maximum clique problem // Handbook of Combinatorial Optimization. /Ed. by D.-Z. Du , P.M. Pardalos. — Kluwer, 1999. — Suppl. Vol. A. — P. 1–74. 5. Kuznetsova A., Strekalovsky A.S. On solving the maximum clique problem // J. of Global Optimization. — 2001. — V. 21, N. 3. — P. 265–288. 6. Motzkin T.S., Straus, E.G., Maxima for graphs and a new proof of a theorem of Tur´an // Canad. J. Math. — 1965. — V. 17. — P. 533–540. 7. Pardalos P.M. Continuous approaches to discrete optimization problems // Nonlinear Optimization and Applications/ Eds. by G.Di. Pillo and F. Giannessi. — New York: Plenum Press, 1996. — P. 313–328. 8. Wilf H. S. The eigenvalues of a graph and its chromatic number //J. London Math. Soc. — 1967. — Vol. 42. — P. 330–332. |