Поиск максимального взвешенного независимого набора вершин на гиперграфе логических ограничений

Задача о поиске независимого множества максимального веса на графе относится к классу NP-полных задач и используется в задачах математического моделирования и оптимизации, которые можно формализовать в терминах теории графов. Разработанный алгоритм поиска максимального взвешенного независимого набора вершин можно применять в рамках оценки пикового тока в комбинационных интегральных схемах и сложнофункциональных блоках небольшой размерности – в пределах нескольких сотен вентилей. В таком случае связанный граф будет являться представлением списка соединений между узлами тестовой схемы, а максимальное взвешенное независимое множество вершин будет соответствовать множеству узлов, которые переключатся одновременно и дадут максимальный мгновенный ток. Для ускоренного поиска независимого множества максимального веса используется комбинация метода ветвей и границ и жадного алгоритма.

1. Wang P., Bohacek S. On the practical complexity of solving the maximum weighted independent set problem for optimal scheduling in wireless networks. Proceedings of the 4th Annual International Conference on Wireless Internet, WICON 2008, Maui, Hawaii, USA, November 17-19, 2008. DOI: 10.1145/1554126.1554145.

2. Dong Y., Goldberg A. V., Noe A., Parotsidis N., Resende M. G. C., Spaen Q. New Instances for Maximum Weight Independent Set from a Vehicle Routing Application. Operations Research Forum, 2021, vol. 2. DOI: 10.1007/s43069-021-00084-x.

3. Borowitz J., Großmann E., Schulz Ch. Optimal Neighborhood Exploration for Dynamic Independent Sets. 2024. 10.48550/arXiv.2407.06912.

4. Zhou L., Wang M., Chen Y. Graph-Based Methods for Simultaneous Switching Noise Analysis and Peak Current Estimation in CMOS Circuits // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, Vol. 42, No. 4, pp. 789–798.

5. Гаврилов С. В., Рыжова Д. И. Алгоритм оценки пикового тока на логическом уровне проектирования на основе анализа распространения логических корреляций в схеме. Вестник Рязанского государственного радиотехнического университета, 2015, выпуск 52, № 2, стр. 56-64. / Gavrilov S. V., Ryzhova D. I. An algorithm for estimating peak current at the logic level of design based on the analysis of the propagation of logical correlations in the circuit. Vestnik of Ryazan State Radio Engineering University, 2015, vol. 52, no. 2, pp. 56-64 (in Russian).

6. Гаврилов С. В. Методы анализа логических корреляций для САПР цифровых КМОП СБИС. М.: РИЦ Техносфера, 2011, 136 с. / Gavrilov S. V. Methods for Logical Correlation Analysis for Digital CMOS VLSI Design. Moscow, Technosfera Research Center, 2011, 136 p. (in Russian).

7. Korhonen T. Lower Bounds on Dynamic Programming for Maximum Weight Independent Set. Available at: https://arxiv.org/pdf/2102.06901, accessed 08.11.2025.

8. Andrade D. V., Resende, M. G. C., Werneck R. F. Fast local search for the maximum independent set problem. Journal of Heuristics, 2012, vol. 18, pp. 525-547. DOI: 10.1007/s10732-012-9196-4.