有向kirkman填充設(shè)計(jì)dkpd{3，539;}，v

1、蘇州大學(xué)碩士學(xué)位論文有向Kirkman填充設(shè)計(jì)DKPD（{3，5}，v）姓名：馬小紅申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：杜北梁20060901有向K i r k n m n ：嗔充設(shè)計(jì)D K P D ( { 3 ，5 4 ) ，v ) A b s 仃a c tD i r e c t e d K i r k m a n P a c k i n g D e s i g n s D K P D ( { 3 ，5 宰) ，DA b s t

2、 r a c tL e tXb ea s e to fvp o i n t s ? Ap a c k i n g ( d i r e c t e dp a c k i n g ) o fX i s ac o l l e c t i o no fs u b s e t s ( o r d e r e ds u b s e t s ) o f X ( c a l l e db l o c k s ) s u c h t h a ta n y

3、 p a i r ( o r d e r e dp a ∞o f d i s t i n c tp o i n t sf i - o m X O C C U T St o g e t h e ri na tm o s to n e b l o c ki nt h ec o l l e c t i o n ．Ap a c k i n g ( d i r e c t e dp a c k i n g ) i sc a l l e dr e

4、s o l v a b l ei f i t s b l o c k s e ta d m i t sa p a r t i t i o ni n t op a r a l l e l c l a s s e s ，e a c hp a r a l l e lc l a s sb e i n ga p a r t i t i o no f t h ep o i n ts e t Z ．A K i r k m a np a c k i n

5、 g d e s i g n ．d 髓o t e dK P D ( { w , s ’} ，∞，i sa r e s o l v a b l ep a c k i n go f av —s e t b yt h em a x i m u m p o s s i b l en u m b e rm p ) o f p a r a l l e l c l a s s e s ，e a c hc o n t a i n i n go n e

6、b l o c ko f s i z e ja n d a l lo t h e rb l o c k so f s i z eW ．Ad i r e c t e d K i r k m a n p a c k i n gd e s i g n , d e n o t e d D K P D ( { w , s ’) ，v ) ，i s a r e s o l v a b l ed i r e c t e dp a c k i n go

7、 f aV —s e t b yt h em a x i m u m p o s s i b l en u m b e r 優(yōu)( 力o f p a r a l l e lc l a s s e s ，e a c h c o n t a i n i n g o n e b l o c k o f s i z e Ja n d a l lo t h e r b l o c k so f s i z e w ．C e r f i y , H

8、o r a ka n d W a l l i si n t r o d u c e dt h e K i r k m a n p a c k i n gd e s i g n C o l b o u r na n d L i n g ，P h i l l i p s ，W a l l i sa n d R e e s d i s c u s s e dt h e e x i s t e n c e o f K P D ( { 3 ，礦)

9、 ，y ) w h e n s ∈{ 2 ，4 ) ．T h es p e c t r u m p r o b l e m f o r X e O ( { 3 ，4 + ) ，v ) h a s b e e na l m o s tc o m p l e t e l ys o l v e da n d b e e nu s e dt oc o n s t r u c tp e r f e c tt h r e s h o l ds c

10、h e m e sw h e n 占≥wb yC a oa n d D uT h e nC a oa n dZ h uc o n s i d e r e dt h e e x i s t e n c eo f K P D ( { 3 ，5 + } ，v ) w h e n v ；2 ( m o d 3 ) ．S i n c et h en u m b e ro fp a r a l l e l c l a s s e s C a nn

11、o t a c h i e v et h ee x p i r e dm a x i m u m , C a oa n dT a n g c o m i d e r e d t h ee x i s t e n c eo f K P D ( { 3 ，4 ”} ，v ) w h e n vE 2 ( m o d 3 ) ．C a o a n d D u c o n s i d e r e d t h e e x i s t e n -c

12、 e o f K P D ( { 4 ，s + ’，力w h e n s ∈{ 5 ，6 ) ．Z h a n ga n dD uc o m p l e t e l ys o l v e dt h es p e c t r u mp r o b l e mf o r t h ed i r e c t e dK i r k m a np a c k i n gd e s i g n D K = P D ( { 3 ，s + } ，v )

13、w h e n s ∈{ 2 , 4 } ．I nt h i sa r t i c l e ，w es h a l lb er e s t r i c t i n go u ra t t e n t i o nt o t h ed i r e c t e dK i r k m a np a c k i n gd e s i g nD K P D ( { 3 ，5 ’) ，v ) ．T h e f o l l o w i n gr e s