Представлен обзор известных решений теоретико-графовых задач, связанных с проблемой сжатия топологии ИС на графе ограничений. Рассмотрены алгоритмы поиска кратчайших путей и циклов отрицательной длины во взвешенном направленном графе. Приведены наиболее значимые работы, опубликованные за последние полстолетия, в которых центральным является вопрос алгоритмической сложности. Выяснены свойства графа ограничений, позволяющие повысить эффективность методов. Даны рекомендации по использованию тех или иных алгоритмов.
1. Cho Y.E. A subjective review of compaction // Proc. of 22nd IEEE Design Automation Conference. - 1985. - P. 396-404.
2. Сотников М.А. Разработка и исследование алгоритмов сжатия топологии стандартных ячеек субмикронных СБИС: Дисс. канд. техн. наук. - ЗАО «Моторола ЗАО». - М., 2004. - 119 с. EDN: NMOLTZ
3. Хачиян Л.Г. Сложность задач линейного программирования. - М.: Знание, 1987. - 32 c.
4. Johnson D.B. Efficient algorithms for shortest paths in sparse networks // Journal of Association for Computing Machinery. - 1977. - Vol. 24, N 1, January. - P. 1-13.
5. Кормен Т. Алгоритмы. Построение и анализ. - М.: МЦНМО, 2004. - 960 c.
6. Dijkstra E.W. A note on two problems in connection with graphs // Nimerische Mathematic 1. - 1959. - P. 269-271.
7. Gilsinn J., Witzgall Ch. A performance comparison of labeling algorithms for calculating shortest path trees // NBS Technical Note 772, U.S. Dept. of Commerce. - 1973. - 22 c.
8. Dial R., Glover F., Karney D., Klingman D. A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees // Networks. - 1979. - Vol. 9, issue 3. - P. 215-248.
9. Ahuja R.K., Mehlhorn K., Orlin J.B., Tarjan R.E. Faster algorithms for the shortest path problem // J. of the Association for Computing Machinery. - 1990. - Vol. 37, N 2, April. - P. 213-223.
10. Henzinger M.R., Klein P., Rao S. Faster shortest-path algorithms for planar graphs // J. of Computer and System Sciences 55. - 1977. - P. 3-23.
11. Bellman R. On a routing problem // Quarterly of applied mathematics. - 1958. - Vol. 16. - P. 87-90.
12. Ford L.R.Jr. Network flow theory // Rand Corporation Report P-923. - 1956. - August. - 13 p.
13. Moore E.F. The shortest path through a maze // Proc. of the International Symposium on the Theory of Switching, Part II. Harvard U. Press (Cambridge, Mass., April 1957). - 1957. - P. 285-292.
14. Yen J.Y. An algorithm for finding shortest routes from all source nodes to a given destination in general network // Quarterly of Applied Mathematics 27, 4. - 1970. - January. - P. 526-530.
15. Pallotino S. Shortest-path methods: complexity, interrelations and new propositions // Networks. - 1984. - Vol. 14. - P. 257-267.
16. Glover F., Klingman D.D., Phillips N.V., Schneider R.F. New polynomial shortest path algorithms and their computational attributes // Management Science: 1985. - Vol. 31, N 9, September. - P. 1106-1128.
17. Dantzig G.B., Blattner W.O., Rao M.R. All shortest routes from a fixed origin in a graph // Proc. of International Symposium on Theory of Graphs (Rome, July 1966). - Gordon and Breach, New-York, 1967. - P. 85-90.
18. Gabow H.N. Scaling algorithms for network problems // Journal of Computer and System sciences 31: 1985. - P. 148-168.
19. Gabow H.N., Tarjan R.E. Faster scaling algorithms for network problems // SIAM Journal on Computing. -1989. - Vol. 18, N 5. - P.1013-1036.
20. Goldberg A.V., Radzik T. A heuristic improvement of the Bellman-Ford algorithm // Applied Mathematics Letters. - 1993. - Vol. 6, N 3. - P. 3-6.
21. Cherkassky B.V., Goldberg A.V., Radzik T. Shortest path algorithms: theory and experimental evaluation // In proceedings of 5th ACM-SIAM Symposium on Discrete Algorithms. - 1994. - P. 516-525.
22. Седжвик Р. Фундаментальные алгоритмы на С. Алгоритмы на графах: Пер. с англ. Роберт Седжвик. - СПб: ООО «ДиаСофтЮП», 2002. - 496 c.
23. Narvаez P., Siu K.-Y., Tzeng H.-Y. New dynamic algorithms for shortest path tree computation // IEEE/ACM Transactions on Networking. - 2000. - Vol. 8, N 6, December. - P. 734-746.
24. Ramalingam G., Reps T. On the computational complexity of dynamic graph problems // Theoretical Computer Science. - 1996. - Vol. 158, Issue 1-2, May. - P. 233-277. EDN: AMCFTM
25. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest path trees // Journal of Algorithms 34. - 2000. - P. 251-281.
26. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest path in digraphs with arbitrary arc weights // J. of Algorithms 49. - 2003. - P. 86-113.
27. Bruce A. Reed. Algorithmic aspects of tree width / Ed. Bruce A. Reed and Clґaudia L. Sales // Recent Advances in Algorithms and Combinatorics. - 2003. - Springer. - P. 85-107.
28. Zhan F.B., Noon C.E. Shortest path algorithms: an evaluation using real road networks // Transportation Science. -1998. - Vol. 32, N 1, February. - P. 65-73.
29. Generating all vertices of a polyhedron is hard / L.Khachiyan, E.Boros, K.Borys et al. // Proc. of the 17th annual ACM-SIAM symposium on Discrete algorithms SODA '06. - 2006, January. - P. 758-765.
30. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 c.
31. Yamada T., Kinoshita H. Finding all the negative cycles in a directed graph // Discrete Applied Mathematics. - 2002. - Vol. 118. - P. 279-291. EDN: ATYXQH
32. Schiele W.L. Compaction with incremental over-constraint resolution // In Proc. 25th ACM/IEEE Design Automation Conference. - 1988. - P. 390-395.
33. Ishima K., Tsukiyama S., Shinoda S. An algorithm to detect positive cycles in a constraint graph for layout compaction // In Proc. IEEE International Symposium on Circuits and Systems. - 1990. - P. 2853-2856.
34. Imai H. Notes on the one-dimensional compaction problem of LSI layouts viewed from network flow theory and algorithms // The transactions of the IECE of Japan. - 1986. - Vol. E 69, N 10, October. - P. 1080-1083.