Microsoft Word - 13.doc


Mathematical Problems of Computer Science 37, 102--107, 2012. 

 
102 

 

 
 

Necessary Conditions for Optimal Permissible Placement 
by the height of the Transitive Directed Tree with One 

Root 
(part second) 

 
Armen Khachaturyan 

 
Yerevan State University 

e-mail: khachaturyanarmen@gmail.com 
 
 

Abstract 
 

The present paper is the second part of the paper [1]. Here we have 
introduced a couple of additional concepts and have obtained some additional 
necessary conditions for the solution of the problem formulated in paper [1]. 
Keywords:   transitive directed graph, 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, “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. 

3. M.R. Garey, D.S. Johnson, Computers and intractability: A guide to the theory of NP-
completeness. San Francisco, CA: W.H. Freeman, 1979. 

4. 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. 

5. 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. 

6. M.R. Garey, D.S. Johnson and L. Stockmeyer, “Some simplified NP-complete graph 
problems”, Theor. Comput. Sci., vol. 1, pp. 237–267.  1976. 

7. Ch.H. Papadimitriou, “The NP-copleteness of the bandwidth minimization problem”, 
Computing, v. 16, pp. 263–270. 1976. 

8. A.V. Petrosyan, S.E. Markosyan, Yu.G. Shukuryan, Mathematical Problems of 
Automation and Projection of Calculating-Machine. Yer., (in Russian). 1977. 

9. 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 
 

103 

10. 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. 

11. Y. Shiloach, “A minimum linear arrangement algorithm for undirected trees” Report, 
Dept. Of Applied Mathematics, Weizmann Institute, Rehovot, Israel. 1976. 

12. D. Adolphson and T.C. Hu, “Optimal linear ordering”, SIAM J. Appl. Math., vol. 25, no. 
3, pp. 403–423.  1973. 

13. C. Berge, The Theory of Graphs and Its Applications. New York: Wiley, 1962. 
 
 
 
 
 
 
 

 
Ø»Ï ³ñÙ³ïáí ïñ³Ý½ÇïÇí ûñÇ»Ýï³óí³Í ͳéÇ Áëï µ³ñÓñáõÃÛ³Ý 

ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñÙ³Ý ³ÝÑñ³Å»ßï å³ÛÙ³ÝÝ»ñ 
(Ù³ë »ñÏñáñ¹) 

 
². ʳã³ïáõñÛ³Ý 

  
²Ù÷á÷áõÙ 

 
êáõÛÝ Ñá¹í³ÍÁ ѳݹÇë³ÝáõÙ ¿ [1] Ñá¹í³ÍÇ ß³ñáõݳÏáõÃÛáõÝÁ: ²Ûëï»Õ Ù»Ýù 
Ý»ñÙáõÍ»É »Ýù áñáß Ýáñ ѳëϳóáõÃÛáõÝÝ»ñ ¨ ëï³ó»É [1] Ñá¹í³ÍáõÙ Ó¨³Ï»ñåí³Í 
ËݹñÇ ÉáõÍÙ³Ý Ñ³Ù³ñ ¨ë ÙÇ ù³ÝÇ ³ÝÑñ³Å»ßï å³ÛÙ³ÝÝ»ñ: 
 
 

Íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîé äîïóñòèìîé ðàññòàíîâêè ïî âûñîòå 
òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì 

(÷àñòü âòîðàÿ) 
 

À. Õà÷àòóðÿí 
  

 Аннотация  
 

Íàñòîÿùàÿ ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì ñòàòüè [1]. Çäåñü ìû ïðèâåëè 
íåêîòîðûå íîâûå êîíöåïèè è ïîëó÷èëè åùå íåñêîëüêî íåîáõîäèìûõ óñëîâèé äëÿ 
ðåøåíèÿ çàäà÷è ñôîðìóëóðîâàííîé â ñòàòüå [1].