Microsoft Word - Armen Khachaturyan_23.doc


Mathematical Problems of Computer Science 33, 183--186, 2010. 

183 
 

 
 
 

The Optimal Permissible Placement by the Height  
of the Transitive Oriented Treecontaining  

One Vertex of Branching 

Armen Khachaturyan 

Yerevan State University, faculty of Informatics and Applied Mathemathics 
e-mail  armenarmenian@mail.ru 

 
Abstract 

In this paper we consider the optimal permissible placement by the height of the 
following type of transitive oriented graphs (the height of the vertex is the number of 
the arcs passing through the vertex): the graph consists of chains of quantity 

2s branching after the end of the chain. The problem was solved by the algorithm 
of ss log  complexity.  

 
 
 
References 
1. В. А. Евстигнеев, “Применение теории графов в программировании”,1985. 
2. А. В. Петросян, С. Е. Маркосян, Ю. Г. Шукурян, “Математические вопросы автоматизации и 

проектирования ЭВМ”.Ереван, 1977. 
3. Г. Г. Геолецян, “Плоское размещение вершин дерева на линии с минимизацией ширины.” ДАН 

Апм ССР, вып. 56, Но-4, стр.202-207, 1973 
4. M.R. Garey, R.L. Graham, D.S. Johnson, and D.E. Knuth “Complexity results for bandwidth 

minimization”,  SIAM J. Appl. Math. 34, pp. 477-495, 1978. 
5. M.R. Garey, D.S. Johnson, and L. Stockmeyer “Some simplified  NP-complete graph problems”, 

Theor. Comput. Sci.1, pp. 237-267, 1976. 
6. Ch. H. Papadimitriou, “The NP-copleteness of the bandwidth minimization problem”, Computing 16, 

pp.263-270, 1976. 

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

 
 
 
 
 
 
 
 
 



184                                                     The Optimal Permissible Placement 
Ø»Ï ×ÛáõÕ³íáñÙ³Ý ·³·³Ã å³ñáõݳÏáÕ ïñ³Ý½ÇïÇí ûñÇ»Ýï³óí³Í  

ͳéÇ ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ ï»Õ³¹ñáõÙÝ Áëï µ³ñÓñáõÃÛ³Ý  

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

²Ù÷á÷áõÙ 
 

 ²ß˳ï³ÝùáõÙ ß³ñ³¹ñí³Í »Ý Ñ»ï¨Û³É ïÇåÇ ïñ³Ý½ÇïÇí ûñÇ»Ýï³óí³Í 
·ñ³ýÝ»ñÇ ûåïÇÙ³É ÃáõÛɳïñ»ÉÇ Ñ³Ù³ñ³Ï³ÉáõÙÝ Áëï µ³ñÓñáõÃÛ³Ý (·³·³ÃÇ 
µ³ñÓñáõÃÛáõÝ ³ë»Éáí ѳëϳÝáõÙ »Ýù ·³·³ÃÇ íñ³Ûáí ³ÝóÝáÕ ³Õ»ÕÝ»ñÇ ù³Ý³ÏÁ)` 
·ñ³ýÁ ϳ½Ùí³Í ¿ ßÕóÛÇó ¨ ßÕóÛÇ í»ñçÇó ×ÛáõÕ³íáñíáÕ 2s  ù³Ý³ÏáõÃÛ³Ùµ 
ßÕóݻñÇó: ÊݹÇñÁ ÉáõÍí»É ¿ ss log  µ³ñ¹áõÃÛ³Ý ³É·áñÇÃÙáí  áñï»Õ s -Á ¹Çï³ñÏí³Í 
·ñ³ýÇ ×ÛáõÕ³íáñíáÕ ßÕóݻñÇ ù³Ý³ÏÝ ¿ :