Microsoft Word - W11_2_.doc Mathematical Problems of Computer Science 37, 88--95, 2012. 88 Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root Armen Khachaturyan Yerevan State University e-mail: khachaturyanarmen@gmail.com Abstract In paper [1] we have introduced a new concept – the transitive directed tree with one root and have formulated its minimum permissible placement problem by the height. In the papers [1] and [2] we have introduced a couple of new concepts and obtained necessary conditions for the solution of that problem. In the present paper using the results and the introduced concepts from the papers [1] and [2] we obtain an optimal polynomial algorithm for the problem solution and present the proof of its optimality. Keywords: a transitive directed graph, an optimal placement. References 1. A. H. Khachaturyan, “Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root”, Mathematical Problems of Computer Science, vol. 36, pp. 104-114, 2012. 2. A. H. Khachaturyan, “Necessary Conditions for Optimal Permissible Placement by the Height of the Transitive Directed Tree with One Root (part second)”, Mathematical Problems of Computer Science, vol. 37, pp. 102-107, 2012. 3. A.H. Khachaturyan, “The optimal permissible placement by the height of the transitive oriented tree containing one vertex of branching”, Mathematical Problems of Computer Science, vol. 30, pp. 71-75, 2008. 4. M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NP- completeness. San Francisco, CA: W.H. Freeman, 1979. 5. F. Gavril, “Some NP-complete problems on graphs,” Proc.11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD, pp. 91-95, 1977. 6. M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth, “Complexity results for bandwidth minimization”, SIAM J. Appl. Math., vol. 34, pp. 477–495. 1978. 7. M.R. Garey, D.S. Johnson and L. Stockmeyer, “Some simplified NP-complete graph problems”, Theor. Comput. Sci., vol. 1, pp. 237–267. 1976. 8. Ch.H. Papadimitriou, “The NP-copleteness of the bandwidth minimization problem”, Computing, v. 16, pp. 263–270. 1976. 9. A.V. Petrosyan, S.E. Markosyan, Yu.G. Shukuryan, Mathematical Problems of Automation and Projection of Calculating-Machine. Yer., (in Russian). 1977. 10. G.G. Geoletsyan, “Flat placement of the vertices of tree with minimization of width”, DAN Arm. SSR, issue 56, no. 4, pp. 202–207 (in Russian). 1973. A. Khachaturyan 89 11. L. M. Goldberg and I. A. Klipker, “Minimum placement of trees on a line,” Technical Report, Physico-Technical Institute of Low Termeperatures, Academy of Sciences of Ukraina SSR, USSR. 1976. 12. Y. Shiloach, “A minimum linear arrangement algorithm for undirected trees” Report, Dept. Of Applied Mathematics, Weizmann Institute, Rehovot, Israel. 1976. 13. D. Adolphson and T.C. Hu, “Optimal linear ordering”, SIAM J. Appl. Math., vol. 25, no. 3, pp. 403–423. 1973. 14. C. Berge, The Theory of Graphs and Its Applications. New York: Wiley, 1962. Ø»Ï ³ñÙ³ïáí ïñ³Ý½ÇïÇí ûñÇ»Ýï³óí³Í ͳéÇ ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñáõÙÝ Áëï µ³ñÓñáõÃÛ³Ý ². ʳã³ïáõñÛ³Ý ²Ù÷á÷áõÙ [1] Ñá¹í³ÍáõÙ Ù»Ýù Ý»ñÙáõÍ»É »Ýù Ýáñ ѳëϳóáõÃÛáõÝ` Ù»Ï ³ñÙ³ïáí ïñ³Ý½ÇïÇí ûñÇ»Ýï³óí³Í Í³é ¨ Ó¨³Ï»ñå»É Ýñ³ Áëï µ³ñÓñáõÃÛ³Ý ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñÙ³Ý ËݹÇñÁ: [1] ¨ [2] Ñá¹í³ÍÝ»ñáõÙ Ù»Ýù Ý»ñÙáõÍ»É »Ýù ÙÇ ß³ñù Ýáñ ѳëϳóáõÃÛáõÝÝ»ñ ¨ ëï³ó»É ³Û¹ ËݹñÇ ÉáõÍÙ³Ý ³ÝÑñ³Å»ßï å³ÛÙ³ÝÝ»ñ: ú·ï³·áñÍ»Éáí [1] ¨ [2] Ñá¹í³ÍÝ»ñáõÙ ëï³óí³Í ³ñ¹ÛáõÝùÝ»ñÁ ¨ Ý»ñÙáõÍí³Í ѳëϳóáõÃÛáõÝÝ»ñÁ, ëáõÛÝ Ñá¹í³ÍáõÙ Ù»Ýù ëï³ó»É »Ýù Ýßí³Í ËݹñÇ ÉáõÍÙ³Ý ûåïÇÙ³É µ³½Ù³Ý¹³Ù³ÛÇÝ ³É·áñÇÃÙÁ ¨ ³é³ç³ñÏ»É Ýñ³ ûåïÇÙ³ÉáõÃÛ³Ý ³å³óáõÛóÁ: Îïòèìàëüíàÿ äîïóñòèìàÿ ðàññòàíîâêà ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì À. Õà÷àòóðÿí Аннотация  ñòàòüå [1] ìû ââåëè íîâóþ êîíöåïöèþ – òðàíçèòèâíî îðèåíòèðîâàííîå äåðåâî ñ îäíèì êîðíåì è ñôîðìóëèðîâàëè çàäà÷ó åãî îïòèìàëüíî äîïóñòèìîé ðàññòàíîâêè ïî âûñîòå.  ñòàòüÿõ [1] è [2] ìû ââåëè íåñêîëüêî íîâûõ êîíöåïöèé è ïîëó÷èëè íåîáõîäèìûå óñëîâèÿ äëÿ ðåøåíèÿ ýòîé çàäà÷è. Èñïîëüçóÿ ðåçóëüòàòû è ââåäåííûå êîíöåïöèè èç ñòàòüåé [1] è [2], ìû â íàñòîÿùåé ñòàòüå ïîëó÷èëè îïòèìàëüíûé ïîëèíîìèàëüíûé àëãîðèòì äëÿ ðåøåíèÿ çàäà÷è è ïðåäñòàâèëè äîêàçàòåëüñòâî åãî îïòèìàëüíîñòè.