D:\User\sbornik_38_pdf\13.DVI


Ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè è âû÷èñëèòåëüíîé òåõíèêè 38, 30{31, 2012.

Ìàêñèìàëüíîå âçâåøåííîå íåçàâèñèìîå ìíîæåñòâî
ïðÿìîóãîëüíèêîâ

Ý.Ò. Ïèëèïîñÿí
Ðîññèéñêî-Àðìÿíñêèé (Ñëàâÿíñêèé) óíèâåðñèòåò

E-mail: eduard.piliposyan@gmail.com

Íà ïëîñêîñòè ðàññìàòðèâàåòñÿ ìíîæåñòâî ïðÿìîóãîëüíèêîâ M , ñòîðîíû êîòîðûõ
ïàðàëëåëüíû êîîðäèíàòíûì îñÿì. Ñ÷èòàåòñÿ, ÷òî âñå îíè ðàñïîëîæåíû âíóòðè
íåêîòîðîé áîëüøîé ïðÿìîóãîëüíîé ðàìêè M è òî÷íî îäíîé ñòîðîíîé îïèðàþòñÿ íà
êàêóþ-òî åå ñòîðîíó. Äîïîëíèòåëüíî ïðåäïîëàãàåòñÿ, ÷òî âñå îíè èìåþò íåêîòîðûé
ïîëîæèòåëüíûé âåñ. Ïðåäëîæåííûé â ðàáîòå ïîëèíîìèàëüíûé àëãîðèòì â ãðàôå
ïåðåñå÷åíèé òàêèõ ïðÿìîóãîëüíèêîâ ñòðîèò íåçàâèñèìîå ìíîæåñòâî ìàêñèìàëüíîãî
âåñà.

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

Çàäà÷à íàõîæäåíèÿ ìàêñèìàëüíîãî íåçàâèñèìîãî ìíîæåñòâà ïðÿìîóãîëüíèêîâ èìååò
øèðîêîå ïðèìåíåíèå â òàêèõ îáëàñòÿõ, êàê èíòåëëåêòóàëüíûé àíàëèç äàííûõ (data min-
ing) [4] è àâòîìàòèçàöèÿ ðàçìåùåíèÿ ìåòîê (automated label placement) [5].

Îñíîâíûå ðåçóëüòàòû
Ïðÿìîóãîëüíèê íàçîâåì ëåâîñòîðîííèì, åñëè åãî ëåâàÿ ñòîðîíà îïèðàåòñÿ íà ëåâîé

ñòîðîíå ïðÿìîóãîëüíîé ðàìêè M. Ìíîæåñòâî ëåâîñòîðîííèõ ïðÿìîóãîëüíèêîâ èç
M îáîçíà÷èì ÷åðåç M L. Àíàëîãè÷íî îïðåäåëÿþòñÿ ìíîæåñòâà ïðàâîñòîðîííèõ M R,
âåðõíèõ M U è íèæíèõ M D ïðÿìîóãîëüíèêîâ.

ßñíî, ÷òî â îáùåì ñëó÷àå âñå ìíîæåñòâà M L; M R; M U ; M D ìîãóò áûòü íåïóñòûìè.
Åñëè òî÷íî i øòóê ( i = 1 ; 2 ; 3 ; 4 ) èç ýòèõ ìíîæåñòâ íå ÿâÿëþòñÿ ïóñòûìè, òî ýòîò
ñëó÷àé ìû íàçîâåì i-ñòîðîííèì ñëó÷àåì è îáîçíà÷èì ëþáîé ïîñëåäîâàòåëüíîñòüþ
ñîîòâåòñòâóþùèõ íåïóñòûì ìíîæåñòâàì áóêâ. Íàïðèìåð, åñëè M L 6= ;; M D 6=
;; M R = M U = ;, òî èìååì äåëî ñ äâóñòîðîííèì ñëó÷àåì LD èëè DL. Îáùèé ñëó÷àé
ïðåäñòàâëÿåòñÿ ëþáîé ïîñëåäîâàòåëüíîñòüþ äëèíû ÷åòûðå (íàïðèìåð LDRU).

 äàííîé ðàáîòå ïðåäëîæåí ïîëèíîìèàëüíûé àëãîðèòì ïîñòðîåíèÿ ìàêñèìàëüíîãî
âçâåøåííîãî íåçàâèñèìîãî ìíîæåñòâà ïðÿìîóãîëüíèêîâ äëÿ âñåõ i - ñòîðîííèõ ñëó÷àåâ
(i = 1 ; 2 ; 3 ; 4 ). Ñëîæíîñòü ïðåäëîæåííûõ àëãîðèòìîâ îáîçíà÷èì ÷åðåç 'i ( n) , ãäå n –
÷èñëî ïðÿìîóãîëüíèêîâ, i = 1 ; 2 ; 3 ; 4 . Áóäåì èñïîëüçîâàòü òàêæå îáîçíà÷åíèå òèïà
'LD ( n) , äëÿ ñëîæíîñòè àëãîðèòìà â ñëó÷àå LD.

Ïðåäëîæåííûå â ðàáîòå àëãîðèòìû èìåþò ñëåäóþùèå ñëîæíîñòè.

'LD ( n) = O
³
n5

´
'DU ( n) = O ( n6 )

3 0



Ý. Ïèëèïîñÿí 3 1

'1 ( n) = O ( n)

'2 ( n) = m a x
³
'LD ( n) ; 'DU ( n)

´
= O ( n6 )

'3 ( n ) = O ( n9 )

'4 ( n) = O ( n11 )

Ñïèñîê ëèòåðàòóðû

[1] Ãýðè Ì., Äæîíñîí Ä., Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è, Ìèð,
Ì., (1982).

[2] T. Asano. Difficulty of the maximum independent set problem on intersection graphs
of geometric objects, In 6th ICTAG, (1991).

[3] J. Kratochvi, J. Nesetril. IND E P E ND E NT SE T and CL IQUE problems in intersection-
de¯ned classes of graphs, Commentationes Mathematicae Universitatis Carolinae, Vol. 31,
No.1, 85–93, (1990).

[4] P. Chalermsook and J. Chuzhoy. M aximum independent set of rectangles, In 20th
annual ACM-SIAM SODA, 892–901, (2009).

[5] P. K. Agarwal, M. J. van Kreveld, and S. Suri. L abel placement by maximum indepen-
dent set in rectangles, Comput. Geom., 11(3–4), 209–218, (1998).