（运筹学与控制论专业论文）网络中的反馈集问题和排序问题.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含 任何他个人或集体已经发表或撰写过的科研成果对本论文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到 本声明的法律责任由本人承担 论文作者签名5 姿芝茎垒日期 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借闭；本人授权山东大学可以将本学位论文全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇 编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名t 弘斗f f i j f 山东大学博士学位论文 网络中的反馈集问题和排序问题 张少强 ( 山东大学数学与系统科学学院，山东，济南2 5 0 1 0 0 ) 指导教师t 李国君教授 中文摘要 在全光网络中餐要通过使用波分复用技术( w d m ) 来充分利用巨大的带宽一 条光纤连接可以同时传输若干逻辑信号，只要保证他们使用不同的波长渡分复用 技术在不远将来的通信领域将起到基础性的重要作用 给定一光学网络，我们可以将它看作一个有向图在这个样一个有向图中，我 们再给定由通讯请求组成的一个集合每一个通讯请求都包含一个发点和一个收点 用于接收和发送信号。对从顶点s 到顶点t 的每个通讯请求，一条从s 到t 的有向 路被选出来作为这个请求的通讯频道这样这些有向路就组成了这组通讯请求的一 个路由每一条路指定一种颜色，使得任两条有公共弧的路着不同的颜色在波分 复用的光学网络中，颜色就对应不同波长的光束因为技术只允许使用有限数量的 波长，所以用于正常分配的色效是有限制的 本文我们主要讨论应用于波分复用技术网络中的关于波长分配，波长转换，及 路由排序中的几类主要组合优化问题。我们同时还讨论了其他几类网络中的优化问 题全文共分七章 第一章引言部分主要介绍波分复用网络的光学模型，相关问题相关主要算法 概念及相关已有结论 为了更充分地利用带宽，一种祓经常使用的技术就是在网络中安装波长转换 器每一个波长转换器都被安装到网络的某个顶点上，使得它能够改变每个输入信 号的传输波长在这篇论文我们就研究在一个给定网络中如何安装尽可能少的波长 转换器，而使得对任何路由所必须的波长数等于两络的拥塞界拥塞界就是网络中 经过任一条边的路的最大数目上述的用于安装波长转换器的顶点集合被w i l f o n g 和w i a k l e r 称为充分集他们还证明了即使在平面图中，找一个最小规模的充分集 也是n p 完备问题在第二章，我们就研究双向全光网络中的充分集同题可以将 山东大学博士学位论文 它转化为求双向网络所对应的基图的最小顶点覆盖问题 推论1 及2 ：在双向网络中，i h 充分案问题存在一个多项式时间的。近似算 法，当且仅当i 小顶点覆盖存在一个多项式时间的o - 近似算法 对双向树网络，给出了有效精确算法；对双向一般图，我们通过修改经典的贪 5 - 算法给出一个2 近似算法 在一般情况下的有向网络，最小充分集问题可以转化为求无向图中的最小反馈 点集问题。如果从一个图中去掉某些顶点后得到的导出子图是无圈图，那么所去的 那些顶点组成的集合就是原图的一个反馈点集因此，我们只需考虑最小反馈点集 问题一个图是系列平行图当且仅当它不含甄细分的子图系列平行图是一种特 殊的平面图，它是由一种系列结构和一种平行结构组合而成的图因为很多网络具 有系列平行的结构，因此在第三章，我们首先给出了求系列平行图中的最小顶点赋 权反馈点集问题的一个线性时间算法对于不带权的反馈点集问题，我们的算法同 样适用我们算法主要通过一种“压缩技爿p 来寻找最优反馈点集我们这里称2 - 度顶点为径直点”，根据下面的定理，我们每次从当前图中去掉一个径赢点。然后 将该径直点是否为最优反馈点集的信息记录在剩余图中 定理6 若图g = e ) 是一个连通的系列平行图且l v l 3 ，则图g 至少含有 一个径直点 定理8 令图g = e ) 是一个2 ，连通的系列平行图，顶点让是与顶点 和圳 相邻的径直点韫设t ，和枷之间没有边相连若分别重新定义g 的边集和顶点集 v = v 一 u ) ，e = ( e 一 ，口) ，( ，叫) ) ) u 扣，加) ， 则得到的新g 仍为2 连通的系列平行圈 定理9 令罄g = ( k e ) 是一个2 一连通的系列平行圈，顶点t l 是与顶点口和叫 相邻的径直点慑设 和 之间有边( ”，t l ，) 相连若分别重新定义g 的边集和顶 点集 v = v 一 t ) ，e = e 一 ( t ，) ，( t t s 加) ， 其i i 得到的新g 或为2 一连通的系列平行圈或为一蠢单边( 口，埘) 定理l o 算法3 - i i i 是求系列平行圈的i 小权反馈点集问题的一个线性时间算 法。 2 山东大学博士学位论文 许多困难的优化问题( ，； 常是n p 完备的】可以在绘定树分解的具有很小树宽的 图中有效解决系列平行图就是一个树宽很小的图，其树宽为2 定义6 图g = ( v e ) 的一个树分解是一对( 五i i n ，t = ( j ，f ) ) ，在这里 ( 咒l i ， 是一姐y 的子集的集合；t = ( j ，f ) 是满足下面性质的一棵树： 1 u 谢五= v 2 对每个边( t ，伽) e 肯定有某个五包含顶点t ，和鼽 只对所有的i ，互k ，若j 落在t 中从i 到k 的唯一路上，则墨n 凰冬，巧 定义7 一个树分解( 五i i n ，t = ( j ，f ) ) 的树宽是m a x t e j i 五i 一1 一个图的 树宽是该圈所有树分解中的最小树宽 在第四章，我们将证明给定一个树分解。如何用动态规划有效解决有界树宽图 中最小反馈点集问题和最小顶点反馈边集问题我们给出动态规划的遵推关系式， 而且很容易得到算法复杂性为线性的如果从一个图中去掉某些边后得到的导出子 图是无圈图，那么所去的那些边组成的集合就是原图的一个反馈边集最小顶点反 馈边集问题就是找一个关联顶点数目最小的反馈边集最小顶点反馈边集问题应用 于流体网络中安装压力表模型 定理1 l 树宽有界图中的最小反馈点集问题和最小顶点反馈边集问题可以用动 态规划践性时间解次， 通话排序问题来源于全光网络中对具有有限持续时间的通讯请求进行路由和排 序它是在一个有带宽限制的网络中对通话( 通讯请求) 指派路径和开始时间使得最 大完成时间( 时间表长) 最短在很多拓扑结构的网络中，通话排序问题都是n p 难 解的在第五章，我们主要将讨论限稿在环形网络和只有一个波长可使用( 简记为 r i n g m i n c s 1 ) 我们设计出一个常数近似比的算法 在波分复用的全光网络中，连接请求( 通讯请求) 必须被指派路和对路着色( 波 长) 使得相交的路着不同的色路着色同题就是给定的连接请求集合指派路和着色 使得用的色数最少如果只有一个波长可用且每次通话持续单位时间，那么通话排 序问题就等价于路着色问题路着色所用的最小色数等于通话排序的时间表长在 第五章我们首先考虑路着色问题，我们先对所有通讯请求进行路由得到路的集合p ， 然后分别按着顺时针和逆时针分别对环形网络中的p 中的路着色最后得到环形网 络中路集给定下的路着色问题的一个1 5 近似算法对树环的路染色问题进行了简 单韵讨论，对硬点度数有界的树环给出了一个近似比有待验证的算法 3 山东大学博士学位论文 定理1 3 对任一环冗和冗上的一路集p ，令u 是囊大两两相交路毒皇数日，算法 h 所闻的颜色数不超过【；u j 对同题r i n g m i n - c s - 1 ，我们可以用最小动态存储分派问题来得到近似解 定理1 5 对任一固定的 0 ，存在一多项式时间算法使得找到r i n g m i n - c s - 1 的路由和排序的时间表长至多( 7 + f ) t + 。 在第六章，我们考虑基于波分复用技术的光学网络中的排序与波长分配问题 给定一级机器和一组e 4 均祷n 步操作加工的工件，该问题就是寻找满足三个条件 的一个时间表最短的排序在波分复用网络中，工件的每步操作代表从一个出发点 到目的点的信息交换，操作的加工时间代表“传输时闻，嚯l 器，代表网络中的波 长” 在波长数目( 即机器数) 固定的情况下，我们证明此问题是n p 难解问题，并且 给出一个多项式时闯近似方案若波长数目不固定，我们根据开放作业排序问题的 近似比证明此问题不存在多项式时闻近似方案 定理1 8 当机器敷固定的时侯。不可中断的波长分配与排序问题是肿难解的 定理1 9 如果机器敷固定，算法i 是解凌不可中断的排序与波长分配问题的 一个多项式时间近似方案 定理2 1 当机器数是输入的一部分，不可中断的排序与波长分配问题不存在多 项式时间近似方案，除非p = n p 在最后一章，我们把由c z u m a j 等人提出的用于网络信息搜集的任务长度可变 的排列问题推广到任务长度可变的多机排序问题证明该问题的判定形式是n p 难 解的，而且对任务最大完成数目的优化形式给出一个近似比小于4 的近似算法 定理2 2 任务长度可变的多机排序问题是n p 难解的 定理2 4 算法7 _ i 是计算求最大完成任务数的任务长度可变的多机排序问题的 一个近似比小于4 的算法 关键词t 波分复用；波长转换；路由；请求；顶点覆盖；反馈点集；反馈边集； 系g j q z 行图；树分解；树宽；动态规划；路着色；排序；波长分配；近似算法；多项 式时间近似方案；时间表长；开放作业；单机排序；多机排序 4 山东大学博士学位论文 f e e d b a c ks e tp r o b l e m sa n d s c h e d u l 玎叮gp r o b l e m si nn e t w o r k s z h a n g s h a o - q i a n g ( s c h o o lo fm a t h s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ，p r c h i n a ) a b s t r a c t i n a l l - o p t i c a ln e t w o r k st h e v a s tb a n d w i d t ha v a i l a b l ei su n t i l i z e dt h r o u g h w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ( w d m ) ：as i n d ep h y s i c a lo p t i c a ll i n kc a nc a r r ys e v e r a ll o g i c a l s i g n a l s ，p r o v i d e dt h a tt h e y a r et r a n s m i t t e do nd i f f e r e n tw a v e l e n g t h s w d m t e c h n o l o g y i no p t i c a ln e t w o r k sw i l lp l a yaf u n d a m e n t a la n dd e t e r m i n a n tr o l ei nt h en e a rf u t u r e t e l e c o m m u n i c a t i o nw o r l d g i v e n 蚰o p t i c a ln e t w o r k w em o d d i ta sad i r e c t e d g r a p h i ns u c ha nu n d e r l y i n g d i r e c t e dg r a p h ，w ea r eg i v e nas e to fc o m m u n i c a t i o nr e q u e s t sf r o mt r a n s m i t t e r st o r e c e i v e r s f o re a c hr e q u e s to fc o m m u n i c a t i o nf r o mn o d est oan o d et ad i r e c t e dp a t h f r o mst oti sc h o s e na sc o m m u n i c a t i o nc h a n n e lt os e r v et h er e q u e s t ar o u t i n gf o ra s e to fc o m m u n i c a t i o nr e q u e s t si ss u c hac o l l e c t i o no fd i r e c t e dp a t h s ac o l o ri st ob e a s s i g n e dt oe a c hp a t hs u c ht h a tn ot w op a t h st h a ts h a r e a tl e a s to n ea r cw i l lb ea s s i g n e d t h es a m ec o l o r i nw d m o p t i c a ln e t w o r k s ，c o l o r sc o r r e s p o n dt ol a s e rb e a m so fd i f f e r e n t w a v e l e n g t h s s i n c et e c h n o l o g ya l l o w st h eu s eo fo n l ya l i m i t e dn u m b e ro fw a v e l e n g t h ， t h et o t a ln u m b e ro fc o b r sa v a i l a b l ef o ra s s i g n m e mi sr e s t r i c t e d i nt h i sd i s s e r t a t i o n ，w es t u d ys e v e r a lm a i nc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s a r i s i n gf r o mw a v e l e n g t ha l l o c a t i o n ，w a v e l e n g t hc o n v e r s i o na n dr e q u e s ts c h e d u l i n gi n w d mn e t w o r k s w ea l s os u r v e ys o m er e s u l t si no t h e rn e t w o r k s t h ed i s s e r t a t i o ni s s p u ti n t os e v e nc h a p t e r s i nc h a p t e rl ，靴i n t r o d u c et h e o p t i c a lm o d e l i nw d mn e t w o r k s ，t h er e l a t e dc o r n - b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，s o m ek e yc o n c e p t sa n dr e l a t e dw o r k o n e t e c h n o l o g yu s u a l l ye m p l o y e di no r d e rt om a k em o r ee f f i c i e n tu s eo ft h ea v a i l - a b l eb a n d w i d t hi st h a to fw a v e l e n g t hc o n v e r t e r s ac o n v e r t e ri sp l a c e di ns o m en o d eo f t h en e t w o r k ，a n dh a st h ea b i l i t yt oa l t e rt h et r a n s m i t t i n gw a v e l e n g t ho fa n yi n c o m i n g 5 山东大学博士学位论文 s i g n a l i nt h i st h e s i s ，w ef i r s ts t u d yt h ep r o b l e m o fp l a c i n ga sf e wc o n v e r t e r sa 8p o s s i - b l ei nag i v e nn e t w o r ks ot h a tt h en u m b e ro fn e c e s s a r yw a v e l e n g t h sf o ra n yr o u t i n gi s e q u a lt ot h ec o n g e s t i o nb o u n d o ft h en e t w o r k s t h ec o n g e s t i o nb o u n di st h em a x i m u m n u m b e ro fp a t h sp a s s i n gt h r o u g ha n ys i n g l ee d g e s u c has e to fn o d e sw h i c ha r eu s e d t op l a c ec o n v e r t e r si sc a l l e das u f f u c i e n ts e td e f i n e db yw i l f o n ga n dw i n k l e r t h e y s h o w e dt h a tf i n d i n gas u f f i c i e n ts e to fn l i i l l m u ms i z ei sn p - c o m p l e t e ，e v e ni np l a n a r i n c h a p t e r2 ，w es t u d yt h es u f f i c i e n ts e tp r o b l e mi nb i - d i r e c t e dn e t w o r k s ，w h i c hc a nb e t r a n s f o r m e di n t om i n i m u mv e r t e xc o v e rp r o b l e m c o r o l l a r y1 ，2 ：nbh i - d i r e c t e dn e t w o r k , t h e 他i s 口p o l y n o m i a l - t i m ec - a p p r o x i m a t i o n | o tt h em i n i m u ms u f f u ：i e n ts e tp r o b l e m ，毽a n do n l y 鹂t h e r e 诮8p o l y n o m i a l - t i m ee a p p r o x i m a t i o n o rt h em i n i m u m v e r t e xc 0 7 3 e rp r o b l e m f o rb i - d i r e c t e dt r e e s ，w ed e s c r i b ea ne t i i e i e ma l g o r i t h m f o rg e n e r a lb i - d i r e c t e d g r a p h s ，w er e v i s et h e t r a d i t i o n a lg r e e d y2 - a p p r o x i m a t i o na l g o r i t h mt oc o m p u t eas u f f i - ， c i e n ts e t , i ng e n e r a ld i r e c t e dn e t w o r k s ，t h es u f f i c i e n ts e tp r o b l e mc a nb et r a n s f o r m e di n t o t h em i n i m u mf e e d b a c kv e k r e xs e t ( f v s ) p r o b l e mf o ru n d i r e c tg r a p h s as u b s e t o ft h ev e r t e xs e to fag r a p hi saf e e d b a c kv e t e xs e to ft h eg r a p hi ft h er e s u l t i n gg r a p hi s a c y c l i ca f t e rr e m o v i n g t h ev e r t e xs u b s e tf r o mt h eg r a p h t o p o l o g yo fm a n yn e t w o r k si s s e r i e s - p a r a l l e l ag r a p h i sc a l l e ds e r i e s - p a r a l l e li fi tc o n t a i n sn oh o m e o m o r p ho fk 4a sa s u b g r a p h s e r i e s - p a r a l l e l 寥a p h sb e l o n gt op l a n a rg r a p h s t h e r e f o r e ，i nc h a p t e r3 ，w e p r o p o s eal i n e a rt i m ee x a c ta l g o r i t h mf o rt h em i n i m u mw e i g h tf v si ns e r i e s - p a r a l l e l g r a p h sb ys o m e c o n t r a c t i o no p e r a t i o n s ”，w h i c hc o n t r a c tt h eg r a p hw h i l ep r e s e r v i n g a l li m p o r t a n tp r o p e r t i e sa n di n f o r m a t i o nr e l e v a n tt ot h e p r o b l e m w ed e f i n eas t r a i g h t v e r t e xt ob ea2 - d e g r e ev e r t e x b y t h ef o l l o w i n gt h e o r e m s ，w ec a nd e l e t ea s t r a i g h t v e r t e xa te a c h s t e pa n d l a b e lu s e f u li n f o r m a t i o na b o u t o p t i m a ls o l u t i o n si nt h er e s i d u l g r a p h t h e o r e m 6 可g = ( ve ) i s8c o n n e c t e ds e r i e s p a r a l l e lg r a p hw i t hi v i 3 t h e n gc o n t a i n sa tl e a s to n es t r a i g h tv e r t e x t h e o r e m8l e tg = ( v e ) b ea2 - c o n n e c t e ds e r i e s p a r a l l e lg r a p ha n dt ds t r a i g h t v e r t e xw i t ht w on e i g h b o r s a n dw s u p p o s et h e r ei sn oe e j o i n i n g a n dm i | w e 山东大学博士学位论文 r e d e f i n egb ys e t t i n g v = 。y 一 让) a n d e = ( e 一 ( 让，t ，) ，( t ，叫) ) ) u 扣，t l ，) ) t h e nt h er e s u l t i n gg r a p hgi ss t i l l 口2 - c o n n e c t e ds e r i e s - p a r a l l e lg r a p h t h e o r e m9l e tg = ( v e ) b e a2 - c o n n e c t e ds e r i e s - p a r a l l e lg r a p ha n d 钍as t r a i g h t v e r t e xw i t ht w on e i g h b o r s 口a n d 叫s u p p o s et h e r ei st a ne d g e ( 口，w ) j o i n i n g 口a n dw 可 埘er e d e f i n eg b ys e t t i n g v = v 一 u ) a n d e = e 一 ( u ，t ，) ，( 缸，伽) ) t h e nt h er e m d t m gg r a p hg 话e i t h e rd2 - c o n n e c t e ds e r i e s - p a r a l l e lg r a p ho ras i n g l ee d g e ( 口，坩) t h e o r e m1 0a l g o r i t h m3 - i i ii sal i n e a ra l g o r i t h mf o rm i n i m u m w e i g h tf v si n s e r i e s - p a r a l l e lg r a p h s m a n yd i f f i c u l t ( o f t e nn p - c o m p l e t e ) o p t i m i z a t i o np r o b l e m s c a nb es o l v e de f f i c i e n t l y o ng r a p h so fs m a l lt r e e - w i d t hw i t hag i v e nt r e e - d e c o m p o s i t i o n d e f i n i t i o n6at r e e d e c o m p o s i t i o no fag r a p hg = ( ve ) 诂np a i r ( 墨ii ，) ，t = ( i ，f ) ) ，w h e r e 五l i ， i s8 f a m i l yo f s u b s e t so f va n d t = ( i ，f ) i snt r e e “地t h ef o l l o w i n gp r o p e r t i e s ： j u 讵，墨= v 霉f o re v e r ye d g e ( v ，w ) e ，t h e r ei ss o m e 咒c o n t a i n i n g 口a n d w 3 f o ra l l t 、j 、k i ，对ji so nt h eu n i q u ep a t h f r o mit oki ntt h e nx t f qx k x 3 d e f i n i t i o n7t h et r e e - w i d t ho fdt r e e d e c o m p o s i t i o n ( 置1i ，) ，t = ( i ，f ) ) i s m a ) c ji 五i 一1 t h et r e e w i d t h0 ，ag r a p h i st h em i n i m u mt r e e w i d t ho 口e ra l lt r e e d e c o m p o s i t i o n s0 lt h eg r a p h i nc h a p t e r4 聪s h o wh o wt os o l v et h em i n i m u mf e e d b a c kv e r t e xs e tp r o b - l e ma n dt h em i n i m u mv e r t e xf e e d b a c ke d g es e tp r o b l e m ( f e s ) e f f i c i e n t l y , u s i n gd y n a m i cp r o g r a m m i n g ，o nat r e e - d e c o m p o s i t i o n f o re a c hp r o b l e m ，w ec a no h - t a i nt h er e c u r s i v er e l a t i o nh o l d i n gb e t w e e ni ta n di t ss u b p r o b l e m t h ef e sp r o b l e m i sm o t i v a t e db yt h ep r o b l e mo fp l a c i n gp r e s s u r em e t e r si nf l u i dn e t w o r k s af e e d b a c k e d g e s e ti sas u b s e to fe d g e si na g r a p h ，w h o s ed e l e t i o nf r o m t h eg r a p hm a k e st h eg r a p h 7 山东大学博士学位论文 ! ! = = ! = = = = = = = = = = = = = = = = = = = = = = 竺= ：= = = = = = = = = = = = = = = = = = = = = = 皇= = = = = 苎= ! ! = ! a c y c f i c t h em i n i m u m v e r t e xf e e d b a c ke d g es e tp r o b l e mi st of i n daf e e d b a c ke d g es e t i n c i d e n tu p o nt h e 贼m r i nn u m b e ro f v e r t i c e s t h e o r e m1 1f v sa n df e si o ”g r a p h sw i t hb o u n d e dt r e e w i d t hc 帆b es o l v e d 讥 l i n e a rt i m e ，r e s p e c t i v e l y , b yu s i n gd y n a m i cp r o g r a m m i n g c a l ls c h e d u l i n g ，w h i c ha r i s e sf r o mr o u t i n ga n ds c h e d u n n gr e q u e s t so fl i m i t e dd u - r a t i o ni na na l l - o p t i c a ln e t w o r k i st h ep r o b l e m o fa s s i g n i n gp a t h sa n ds t a r t i n gt i m e st 0 c a l l s ( c o m m u n i c a t i o nr e q u e s t s ) i na n e t w o r kw i t hb a n d w i d t hr e s e r v a t i o ns u c ht h a tt h e m a x i m u mc o m p l e t i o nt “i i n e ( m a k e s p a n ) i sm i n i m i z e d i nc h a p t e r5 ，w eo n l yc o n s i d e r ”t h ep r o b l e mw i t hr e s t r i c t e do i lo 艟a v a i l a b l e - w a v e l e n g t hi nr i n gn e t w o r k & 。w ep r o p o s e a nc o n s t a n ta p p r o x i m a t i o na l g o r i t h mf o ri t i nw d m a l l - o p t i c a ln e t w o r k s ，c o n n e c t i o nr e q u e s t sm u s tb ea s s i g n e dp a t h sa n d c o l o r sr w a v e l e n g t h s ) s u c ht h a ti n t e r s e c t i n gp a t h sr e c e i v ed i t t e r e n tc o l o r s p a t hc o l o b n gi st om i n i m i z et h en u m b e ro fc o l o r su s e d i nt h ec a s eo fu n i tc a l ld u r s t i o n sa n d o n ew a v e l e n g t ha v a i l a b l e ，c a l ls c h e d u l i n gi se q u i v a l e n tt op a t hc o l o r i n g ：c o l o r ss i m p l y c o r r e s p o n dt ot i m es t e p s i nc h a p t e r5 w ef i r s t c o n s i d e rt h ep a t hc o l o r i n gp r o b l e m w ec a nr o u t et h eg i v e ns e to fc a l l sa n do b t a i nas e tp o fp a t h s t h ec o l o rc l a s s e s8 , r e c o n s t r u c t e do n eb yo n ei nt h ef o u o w i n gw a y ：s c a n n i n gt h ep a t h sa l o n gt h er i n g 冗i n t h ec l o c k w i s ea n dc o u n t e r c l o c k w s i ed i r e c t i o i l s r e s p e c t i v e l y , w eg r e e d i l ys e l e c tap a t hi n t h er e s i d u a lp a t h si n t ot h ec u r r e n tc l a s ss u c ht h a tt h ep a t hi sd 两o i n tf r o ma n yp a t h i nt h ec u r r e n tc l a s s t h es e to fp a t h si sg i v e n i ti sa1 5a p p r o x i m a t i o na l g o r i t h mf o r t h ep a t hc o l o r i n gp r o b l e mi nr i n gn e t w o r k s t h e o r e m1 3f o ra n y w 冗a n das e tp o f p a t h so 优r 冗，a l g o r i t h m5 - iu s e 8n o m o r l 2t h a n 【；u jc o l o r s ，w h e r eui st h em a x i m u mn u m b e ro f p a i r w t s ei n t e r s e c t i n g p a t h s f o rk i n g - m i n c s - 1 w el 雠m i n i m u md y n a m i cs t o r a g ea l l o c a t i o np r o b - l e mt oa p p r o x i m a t ei t t h e o r e m1 5f o r a n yf i x e de 0 ，t h e r ee x i s t sap o l y n o m i a l - t i m ea l g o r i t h mt h a t f i n d sar o u t i n ga n d a s c h e d u l i n g 如rr i n g m i n c s 一1h a v i n gm a k e s t m na tm o s t ( 7 + ) p i n c h a p t e r6 ，w ec o n s i d e rt h es c h e d u l i n ga n dw a v e l e n g t ha s s i g n m e n t ( s w a ) p r o b l e m ，w h i c h a l s oa r i s e si no p t i c a lw d mn e t w o r k s g i v e nas e to f p r o c e s s o r s a n das e to fj o b se a c hc o n s i s t i n go fno p e r a t i o n s ，t h es w a p r o b l e m i st of i n das c h e d u l e 8 山东大学博士学位论文 s oa st om i n i m i z et h em a k e s p a n ，w h i c hi st h et i m eb yw h i c ha l lj o b sa r ec o m p l e t e d ， s u b j e c tt ot h r e ec o n s t r a i n t s i nap a c k e t - s w i t c h e do p t i c a lw d m n e t w o r k ，a no p e r a t i o n c o r r e s p o n d st ot h ea m o u n to ft r a f f i ct ob et r a n s m i t t e df r o mas o n r e et oad e s t i n a t i o n a n dt h ep r o c e s s i n gt i m eo f8 2 1o p e r a t i o nr e p r e s e n t st h e “t r a n s m i s s i o nt i m e ”t h et e r m “p r o c e s s o r c o r r e s p o n d st o r a v e l e n g t h i nt h en e t w o r k w e o n l ys t u d y t h en o n - p r e e m p t i v ec 8 s e i ft h en u m b e ro fw a v e l e n g t h s ( p r o c e s s o r s ) i saf i x e dc o n s t a n t ，w ep r o v et h a tt h es w a p r o b l e m i sn p - h a r da n d p r e s e n tap o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e ( p t a s ) t os o l v ei t i ft h en u m b e ro fp r o c e s s o r si sn o tf i x e d ， w ep r o v et h a tt h e r ed o e sn o te x i s ta na p p r o x i m a t i o ns c h e m ef o rt h ep r o b l e mb yt