D:\sbornik\...\TPEL.DVI


Mathematical Problems of Computer Science 32, 23{26, 2009.

T he M inimum Linear Ar r angement P r oblem on

B ipar tite ¡-or iented Gr aphs

L e vo n R . R a fa ye lya n

Yerevan State University
levonr@synopsys.com

Abstract

In general case the minimum linear arrangement (MINLA) problem is NP-complete.
It is NP-complete also for bipartite graphs. In this paper it is proved that a minimum
linear arrangement for bipartite ¡-oriented graphs can be found in polynomial time.
The formula for the cost of optimal arrangement is given as well.

Refer ences

[1 ] M. R . Ga r e y, D . S . Jo h n s o n ,Computers and Intractability. A g u id e t o t h e t h e o r y o f
N P -c o m p le t e n e s s . Fr e e m a n a n d Co m p a n y, 1 9 7 9 .

[2 ] S . E ve n , Y . S h ilo a h , N P -c o m p le t e n e s s o f s e ve r a l a r r a n g e m e n t p r o b le m s , R e p o r t N o . 4 3 ,
D e p t . o f Co m p u t e r S c ie n c e , Te c h n io n , H a ifa , Is r a e l, 1 9 7 5 .

ØÇÝÇÙ³É ·Í³ÛÇÝ Ñ³Ù³ñ³Ï³ÉáõÙ ËݹñÇ ÉáõÍáõÙÁ »ñÏÏáÕÙ³ÝÇ
¡ -ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñÇ Ñ³Ù³ñ

È. è³ý³Û»ÉÛ³Ý

²Ù÷á÷áõÙ

¶ñ³ýÇ ÙÇÝÇÙ³É ·Í³ÛÇÝ Ñ³Ù³ñ³Ï³ÉáõÙ ËݹÇñÁ ÁݹѳÝáõñ ¹»åùáõÙ NP- ÉñÇí ¿: ²ÛÝ
NP- ÉñÇí ¿ ݳ¨ »ñÏÏáÕÙ³ÝÇ ·ñ³ýÝ»ñÇ Ñ³Ù³ñ: ²Ûëï»Õ ³å³óáõóí³Í ¿, áñ »ñÏÏáÕÙ³ÝÇ
¡ -ÏáÕÙÝáñáßí³Í ·ñ³ýÝ»ñÇ Ñ³Ù³ñ ÙÇÝÇÙ³É ·Í³ÛÇÝ Ñ³Ù³ñ³Ï³Éáõ٠ϳñ»ÉÇ ¿ ·ïÝ»É
µ³½Ù³Ý¹³Ù³ÛÇÝ Å³Ù³Ý³ÏáõÙ: îñí³Í ¿ ݳ¨ ûåïÇÙ³É ÉáõÍÙ³Ý ³ñÅ»ùÝ»ñÇ Ñ³ßí³ñÏáÕ
µ³Ý³Ó¨Á:

2 3