МИНИМАЛЬНЫЕ НУМЕРАЦИИ КОРНЕВЫХ ОРИЕНТИРОВАННЫХ ДЕРЕВЬЕВ С ВЫДЕЛЕННОЙ ВЕРШИНОЙ |
| 5 | |
| 2012 |
| 519.1 | |||
| 171-178 | нумерация, однокорневое ориентированное дерево |
| Рассматривается задача построения нумерации вершин однокорневого ориентированного дерева, минимизирующей сумму номера выделенной вершины и среднего расстояния между номерами всех пар смежных вершин. Приводится алгоритм ее решения с трудоемкостью O ( n log n ). |
 |
| 1 . Adolphson D., Hu T.C. Optimal linear ordering // SIAM J. Appl. Math. 1973. V. 25. № 3. P. 403–423. 2 . Иорданский М.А. Оптимальные нумерации вершин графов // Математические вопросы кибернетики. Вып. 10. М.: Наука, 2001. С. 83–102. 3 . Shiloach Y.A. A minimal linear arrangement algorithm for undirected trees // SIAM J. Comput. 1979. V. 8. № 1. P. 15–32. 4 . Шейдвассер М.А. О длине и ширине размещений графов в решетках // Проблемы кибернетики. Вып. 29. М.: Наука, 1974. С. 63–102. |