Многоуровневая декомпозиция гиперграфовых структур

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

Литература.

[AAZ] Зыков А.А. Гиперграфы. Успехи математических наук. 1974. 6(180). С. 89 - 154

[AB] Бершадский А.М. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. - Саратов: СГУ, 1983.

[BBFR] Bette Bultena, Frank Ruskey. "Venn Diagrams with Few Vertices", 1998.

[BKLR1] Коробков Б.П., Растригин Л.А. Рандомизированные методы разрезания графов. Часть 1. Изв. АН СССР. Техническая кибернетика, № 3, 1982, с.163-172

[BKLR2] Коробков Б.П., Растригин Л.А. Рандомизированные методы разрезания графов. Часть 2. Изв. АН СССР. Техническая кибернетика, № 4, 1982, с.120-126

[BKSL] B. W. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291-307, 1970.

[BHRL] Bruce Hendrickson, Robert Leland. "A Multilevel Algorithm for Partitioning Graphs", 1993

[CAAK1] C. J. Alpert and A. B. Kahng. Multi-way partitioning via space-filling curves and dynamic programming. In Proc. of the Design Automation Conference, pages 652-657, 1994.

[CAAK3] C. J. Alpert, J. H. Huang, and A. B. Kahng. Multilevel circuit partitioning. In Proc. of the 34th ACM/IEEE Design Automation Conference, 1997.

[CFRM] C. M. Fiduccia and R. M. Mattheyses. A linear time heuristic for improving network partitions. In In Proc. 19th IEEE Design Automation Conference, pages 175-181, 1982.

[CYCC] C. W. Yeh, C. K. Cheng, and T. T. Lin. A general purpose multiple-way partitioning algorithm. In Proc. of the Design Automation Conference, pages 421-426, 1991.

[DB1] Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995, 64 c.

[DB2] Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984

[DBNS1] Батищев Д.И., Старостин Н.В. k-разбиение графов. Вестник ННГУ "Математическое моделирование и оптимальное управление", Н.Новгород, 2000 г., стр. 37-25.

[DBNS4] Батищев Д.И., Старостин Н.В. Способы повышения эффективности генетического поиска оптимального k-разбиения графа. Воронеж. Межвузовский сборник науч. трудов "Прикладные задачи моделирования и оптимизации", 2000 г., Часть 2, стр. 4-17.

[DBNS6] Д.И. Батищев, Н.В. Старостин, А.В. Филимонов. Многоуровневый генетический алгоритм решения задачи декомпозиции гиперграфа. Известия СПбГЭТУ "ЛЭТИ". Серия "Информатика управление и компьютерные технологии"

[DBNS7] Д.И. Батищев, Н.В. Старостин, А.В. Филимонов. "Многоуровневый алгоритм решения задачи компоновки интегральных схем". "Системы управления и информационные технологии", г.Воронеж, 2007г

[DBSV2] Батищев Д.И., Власов  С.Е., Старостин Н.В., Филимонов А.В.  Новый подход к представлению  гиперграфовых структур. Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. Вып. 14, 2005 г., стр. 67-78

[DBYL] Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Издательство Воронежского государственного университета, 1997

[DSBK] D. G. Schweikert and B.W. Kernighan. A proper model for the partitioning of electrical circuits. In Proc. ACM/IEEE Design Automation Conference, pages 57-62, 1972.

[GKVK1] George Karypis, Vipin Kumar. "Parallel Multilevel Graph Partitioning", 1995

[GKVK2] George Karypis, Rajat Aggarwal, Vipin Kumar, and Shashi Shekhar. Multilevel hypergraph partitioning: Application in VLSI domain. In Proceedings of the Design and Automation Conference, 1997.

[GKVK3] G. Karypis and V. Kumar. hMETIS 1.5: A hypergraph partitioning package. Technical report, Department of Computer Science, University of Minnesota, 1998

[GKVK4] G. Karypis and V. Kumar. Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of Supercomputing, 1998.

[GKVK5] George Karypis and Vipin Kumar."Multilevel k-way Hypergraph Partitioning"

[GKVK6] Schloegel K., Karypis G., Kumar V. Multilevel diffusion schemes for repartitioning of adaptive meshes. Technical Report 97-013, University of Minnesota, Department of Computer Science, 1997

[HPSK] Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985

[HSST] Horst D. Simon and Shang-Hua Teng. How good is recursive bisection? Technical Report RNR-93-012, NAS Systems Division, NASA, Moffet Field, CA, 1993.

[KSGK] Kirk Schloegel, George Karypis, and Vipin Kumar. "Graph Partitioning for High Performance Scientific Simulations", 2000.

[LG3] Laszewski, G. A Genetic Algorithm for the Graph Partitioning Problem. Master's thesis, University of Bonn, Nov., 1990

[MGDD] Гэри М., Джонсон Д. Вычислительные алгоритмы и труднорешаемые задачи, М.: Мир, 1982.

[NK] Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978

[NSAF2] Старостин Н.В., Филимонов  А.В. Аспекты программной реализации  гиперграфов. Сборник научных  статей НГТУ 2005 "Информационные  технологии", том 56, с. 80-89

[NSGK] Navaratnasothie Selvakkumaran and George Karypis. "Multi-Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization", 2005