D:\sbornik\...\tpel\tpel.DVI Mathematical Problems of Computer Science 36, 51{56, 2012. A N ote on M aximum Weight I ndependent Set in Outer -r ectangle Gr aph E d u a r d T. P ilip o s ya n Russian-Armenian State University e-mail: eduard.piliposyan@gmail.com Abstract An outer-rectangle graph is the intersection graph of rectangles lying inside a rect- angular box and having exactly one edge on the boundary of the box. We present a polynomial-time algorithm for the problem of computing a maximum weight indepen- dent set in 2-side outer-rectangle graphs where any two rectangles lying on same edge of box do not intersect. Keywords: Weighted independent set, rectangle graphs, dynamic programming. Refer ences [1 ] P . Ch a le r m s o o k a n d J. Ch u z h o y.\ Ma xim u m in d e p e n d e n t s e t o f r e c t a n g le s " . In 20th annual ACM -SIAM SOD A, p p . 8 9 2 { 9 0 1 , 2 0 0 9 . [2 ] P . K . A g a r wa l, M. J. va n K r e ve ld , a n d S . S u r i. \ L a b e l p la c e m e n t b y m a xim u m in d e - p e n d e n t s e t in r e c t a n g le s " . Comput. Geom., 1 1 ( 3 { 4 ) : p p .2 0 9 { 2 1 8 , 1 9 9 8 . [3 ] S . D o e r s c h le r a n d H . Fr e e m a n . \ A r u le -b a s e d s ys t e m fo r d e n s e -m a p n a m e p la c e m e n t " . Communications of the ACM , 3 5 ( 1 ) , p p . 6 8 { 7 9 , 1 9 9 2 . [4 ] R . J. Fo wle r , M. S . P a t e r s o n , a n d S . L . Ta n im o t o . \ Op t im a l p a c kin g a n d c o ve r in g in t h e p la n e a r e N P -c o m p le t e " . Inform. P rocess. L ett., 1 2 ( 3 ) , p p .1 3 3 { 1 3 7 , 1 9 8 1 . [5 ] T. A s a n o . D i± culty of the maximum independent set problem on intersection graphs of geometric objects. In 6 t h ICTA G, 1 9 9 1 . [6 ] P . B e r m a n , B . D a s Gu p t a , S . Mu t h u kr is h n a n , a n d S . R a m a s wa m i. \ E ± c ie n t a p p r o xi- m a t io n a lg o r it h m s fo r t ilin g a n d p a c kin g p r o b le m s wit h r e c t a n g le s " . J . Algorithm, 4 1 , 2 0 0 1 . [7 ] L . L e win -E yt a n , J. N a o r , a n d A . Or d a . \ A d m is s io n c o n t r o l in n e t wo r ks wit h a d va n c e r e s e r va t io n s " . Algorithmica, 4 0 ( 4 ) : p p .2 9 3 { 3 0 4 , 2 0 0 4 . [8 ] T. M. Ch a n a n d S . H a r -P e le d . \ A p p r o xim a t io n a lg o r it h m s fo r m a xim u m in d e p e n d e n t s e t o f p s e u d o -d is ks " . In 25th annual ACM SOCG, p p . 3 3 3 { 3 4 0 , 2 0 0 9 . [9 ] G. H . Ch e n , M. T. K u o , a n d J. P . S h e u . \ A n o p t im a l t im e a lg o r it h m fo r ¯ n d in g a m a xim u m we ig h t in d e p e n d e n t s e t in a t r e e " . B IT, vo l. 2 3 , p p . 3 5 3 | 3 5 6 , 1 9 8 8 . [1 0 ] G. Fr a h lin g , U . Fa ig le .A combinatorial algorithm for weighted stable sets in bipartite graphs. D is c r e t e a p p lie d m a t h e m a t ic s , 2 0 0 6 . 5 1 5 2 A Note on Maximum Weight Independent Set in Outer-rectangle Graph [1 1 ] M. P a l a n d G. P . B h a t t a c h a r je e , A sequential algorithm for ¯nding a maximum weight k-independent set on interval graphs, Intern. J . Computer M athematics, vo l. 6 0 , p p . 2 0 5 -2 1 4 , 1 9 9 6 . ²é³í»É³·áõÛÝ Ïßéáí ³ÝÏ³Ë µ³½ÙáõÃÛáõÝÝ»ñ ³ñï³ùÇÝ áõÕÕ³ÝÏÛáõÝÝ»ñÇ ·ñ³ýÝ»ñáõÙ ¾. öÇÉÇåáëÛ³Ý ²Ù÷á÷áõÙ ²ñï³ùÇÝ áõÕÕ³ÝÏÛáõÝÝ»ñÇ ·ñ³ýÝ ³ÛÝåÇëÇ áõÕÕ³ÝÏÛáõÝÝ»ñÇ Ñ³ïáõÙÝ»ñÇ ·ñ³ý ¿, áñáÝù µáÉáñÁ Ý»ñ³éí³Í »Ý ÙǨÝáõÛÝ áõÕÕ³ÝÏÛáõÝ ßñç³Ý³ÏÇ Ù»ç ¨ áñáÝó ×Çßï Ù»Ï ÏáÕÙÁ Ñ»Ýí³Í ¿ ³Û¹ ßñç³Ý³ÏÇ áñ¨¿ ÏáÕÙÇ íñ³: ²ß˳ï³ÝùáõÙ Ý»ñϳ۳óí³Í ¿ ³ñï³ùÇÝ áõÕÕ³ÝÏÛáõÝÝ»ñÇ ·ñ³ýáõÙ ³é³í»É³·áõÛÝ Ïßéáí ³ÝÏ³Ë µ³½ÙáõÃÛáõÝ Ï³éáõóáÕ µ³½Ù³Ý¹³Ù³ÛÇÝ µ³ñ¹áõÃÛ³Ùµ ³É·áñÇÃÙ ³ÛÝ ¹»ù»ñÇ Ñ³Ù³ñ, »ñµ áõÕÕ³ÝÏÛáõÝÝ»ñÁ Ñ»Ýí³Í »Ý ßñç³Ý³ÏÇ ÏáÕÙ»ñÇó ÙdzÛÝ »ñÏáõëÇ íñ³, ¨ ßñç³Ý³ÏÇ ÙǨÝáõÛÝ ÏáÕÙÇÝ Ñ»Ýí³Í áõÕÕ³ÝÏÛáõÝÝ»ñÁ ã»Ý ѳïíáõÙ: Íåçàâèñèìûå ìíîæåñòâà ìàêñèìàëüíîãî âåñà â âíåøíå ïðÿìîóãîëüíûõ ãðàôàõ Ý. Ïèëèïîñÿí Àííîòàöèÿ Âíåøíåïðÿìîóãîëüíûé ãðàô - ýòî ãðàô ïåðåñå÷åíèé ïðÿìîóãîëüíèêîâ, êîòîðûå âñå ðàñïîëîæåíû âíóòðè íåêîòîðîãî ïðÿìîóãîëüíèêà - ðàìêè, è òî÷íî îäíà ñòîðîíà êîòîðûõ íàõîäèòñÿ (îïèðàåòñÿ) íà êàêîé-òî ñòîðîíå ðàìêè.  ðàáîòå ïðåäñòàâëåí ïîëèíîìèàëüíûé àëãîðèòì ïîñòðîåíèÿ íåçàâèñèìîãî ìíîæåñòâà ìàêñèìàëüíîãî âåñà â âíåøíåïðÿìîóãîëüíîì ãðàôå â ñëó÷àå, êîãäà ïðÿìîóãîëüíèêè îïèðàþòñÿ òîëüêî íà äâå ñòîðîíû ðàìêè, è îïèðàþùèåñÿ íà îäíó è òó æå ñòîðîíó ðàìêè ïðÿìîóãîëüíèêè íå ïåðåñåêàþòñÿ.