С.В. Листровой, д-р техн. наук
Украинский госуниверситет железнодорожного транспорта
(Украина, 61050, Харьков, пл. Фейербаха, 7,
тел. (050) 9355042, е-mail:
А.В. Сидоренко
Samsung Electronics Ukraine Company,
LLC Samsung R&D Institute Ukraine
(Украина, 01302, Киев, ул. Льва Толстого, 57,
тел. +380509800852, е-mail:
Е.С. Листровая, канд. техн. наук
Национальный аэрокосмический университет им. Н.Е. Жуковского
(Украина, 61070, Харьков, ул. Чкалова, 17,
е-mail:
АННОТАЦИЯ
Запропоновано метод пошуку найбільших максимальних незалежних множин неорієнтованого зв’язкового графа, який дозволяє при числі вершин в графі, що не перевищує 120, і щільності ребер у діапазоні від 0,067 до 0,9, вирішувати задачу визначення найбільших максимальних незалежних множин за поліноміальний час. При подальшому збільшенні числа вершин і зменшенні щільності ребер в графі алгоритм має експоненціальну складність, що в середньому не перевищує O (20,4n), яка має тенденцію до зменшення при збільшенні щільності ребер в графі, де n — число вершин графа.
КЛЮЧЕВЫЕ СЛОВА:
максимальна незалежна безліч, кліка, вершинне покриття.
СПИСОК ЛИТЕРАТУРЫ
1. Harary F., Ross I.C. A Procedure for Clique Detection Using the Group Matrix // Sociometry. — 1957.— Vol. 20. — P. 205—215.
2. Butenko S., Wilhelm W.E. Clique-detection models in computational biochemistry and genomics // European Journal of Operational Research. — 2006. — Vol. 173.— P. 1—17.
3. Raymond J.W., Willett P. Maximum common subgraph isomorphism algorithms matching chemical structures // Journal of Computer-Aided Molecular Design.—2002.—Vol. 16.—P. 521—533.
4. Varmuza K., Penchev P.N., Scsibrany H. Maximum common substructures of organic compounds exhibiting similar infrared spectra // J. Chem. Inf. Comput. Sci.—1998. —Vol. 38.—P. 420—427.
5. Horaud R., Skordas T. Stereo correspondence through feature grouping andmaximal cliques //IEEE Trans. Pattern Anal. Mach. Intell. — 1989. — Vol. 11, № 11.
6. Pelillo M., Siddiqi K., Zucker S.W. Matching hierarchical structures using association graphs // IEEE Trans. Pattern Anal. Mach. Intell. — 1999. — Vol. 21, № 11.
7. Shearer K., Bunke H., Venkatesh S. Video indexing and similarity retrieval by largest common subgraph detection using decision trees. IDIAP-RR 00-15, Dalle Molle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland, 2000.
8. Shirinivas S.G., Vetrivel S., Elango N.M. Application of graph theory in computer science an overview // International Journal of Engineering Science and Technology.—2010.—Vol. 2, № 9. —P. 4610—4621.
9. Селиверстов A.В., Любецкий В.А. Алгоритм поиска консервативных участков нуклеотидных последовательностей // Информационные процессы. — 2006. — 6, №1.— C. 33—36.
10. Bahadur D.K.C., Akutsu T., Tomita E. et al. Point matching under non-uniform distortions and protein side chain packing based on efficient maximum clique algorithms // Genome Inform. —2002. —Vol. 13. — P. 143—152.
11. Carr R.D., Lancia G., Istrail S. Branch-and-cut algorithms for independent set problems: integrality gap and application to protein structure alignment. Technical report, Sandia National Laboratories, Albuquerque, NM (US); Sandia National Laboratories, Livermore, CA (US), September 2000.
12. Harley E., Bonner A., Goodman N. Uniform integration of genome mapping data using intersection graphs // Bioinformatics. — 2001. — Vol. 17. — P. 487—494.
13. Samudrala R., Moult J. A graph-theoretic algorithm for comparative modeling of protein structure // J. Mol. Biol.— 1998.— Vol. 279.— P. 287—302.
14. Tomita E., Akutsu T., Hayashida M. et al. Algorithms for computing an optimal protein threading with profiles and distance restraints // Genome Informatics.—2003.—Vol. 14.—P. 480—481.
15. Bahadur D.K.C., Tomita E., Suzuki J. et al. Protein sidechain packing problem: a maximum edge-weight clique algorithmic approach // J. Bioinform Comput. Biol.—2005.—Vol. 3.—P. 103—126.
16. Jianer C., Iyad K.A., Ge X. Improved Parameterized Upper Bounds for Vertex Cover. — Elsevier: Theoretical Computer Science. — 2010. —Vol. 411. — P. 3736—3756.
17. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph // Comm of ACM. — 1973.— Vol. 16. — P. 575—577.
18. Fomin F.V., Grandoni F., Kratsch D. Measure and conquer: a simple O(20.288n ) independent set algorithm//Proc. of the 17th Annual ACM-SIAM Symp. on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22- 26, 2006, P. 18—25. ACM Press, 2006.
19. Robson J.M. Algorithms for maximum independent set // Journal of Algorithms.—1986.— Vol. 7, No. 3.— P. 425—440.
20. Tarjan R.E., Trojanowski A.E. Finding a Maximum Independent Set // SIAM Journal on Computing.— 1977.— Vol. 6. —P. 537—546.
21. Moon J.W., Moser L. On cliques in graphs // Israel J. Math.—1965.—Vol. 3.— P. 23—28.
22. Pardalos P.M., Xue J. The maximum clique problem // Journal of Global Optimization.— 1994. —Vol. 4. —P. 301—328.
23. Олемской И.В., Фирюлина О.С. Алгоритм поиска наибольшего независимого множества // Вестн. С.-Пб. ун-та. Сер. 10: Прикладная математика, информатика, процессы управления. —2014. —Вып. 1. — С. 81—91.
24. Плотников А.Д. Эвристический алгоритм для поиска наибольшего независимого множества // Кибернетика и системный анализ. — 2012. — № 5. — С. 41—48.
25. Листровой С.В. Метод перечисления максимальних независимых множеств в произвольных неориентированных графах // Электрон. моделирование.—2014.—36, № 1.—С. 3—17.
26. Listrovoy S.V., Minukhin S.V. General Approach to Solving Optimization Problems in Distributed Computing Systems and Theory of Intelligence Systems Construction // Journal of automation and information sciences. — 2010. — Vol. 42, No. 3. — P. 30—46.
27. Листровой С.В., Минухин С.В. Общий подход к решению задач оптимизации в распределенных вычислительных системах и теории построения интеллектуальных систем // Проблемы управления и информатика. —2010. — № 2. — С. 65—82.
ЛИСТРОВОЙ Сергей Владимирович, д-р техн. наук, профессор Украинского государственного университета железнодорожного транспорта (г. Харьков). В 1972 г. окончил Харьковское высшее военное командно-инженерное училище. Область научных исследований — задачи дискретной оптимизации и теории графов и их приложения к анализу вычислительных систем и сетей.
СИДОРЕНКО Андрей Владимирович, вед. инженер-программист фирмы Samsung Electronics Ukraine Company, LLC Samsung R&D Institute Ukraine (г. Киев). В 2001 г. окончил Харьковский военный университет. Область научных исследований — задачи дискретной оптимизации и теории графов и их приложения к анализу вычислительных систем и сетей.
ЛИСТРОВАЯ Елена Сергеевна, канд. техн. наук, доцент кафедры экономики и маркетинга Национального аэрокосмического университета им. Н.Е. Жуковского (г. Харьков), который окончила в 1998 г. Область научных исследований — применение информационных систем в экономической сфере деятельности.