没有合适的资源?快使用搜索试试~ 我知道了~
可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)613-624www.elsevier.com/locate/entcs列表着色问题的毛罗·卢奇1,2格雷西拉·纳西尼1,3丹尼尔·塞弗恩1,4部门。deMatematica,FCEIA,罗萨里奥国立大学,阿根廷CONICET,阿根廷摘要式图中的着色问题已经被用来对各种各样的实际应用进行建模。特别地,列表着色问题推广了众所周知的图着色问题,对于该图着色问题已经开发了许多精确的算法。在本文中,我们提出了一个分支和价格算法的加权版本的列表着色问题,基于一个开发的Mehrotra和Trick(1996年)的图形着色问题。此版本考虑与每种颜色关联的非负权重,并且需要将颜色从预定义列表分配给每种顶点,因此分配的颜色的权重之和最小。计算实验显示了我们的方法的良好性能,能够舒适地解决那些图形达到70个垂直度的实例。这些经验还表明,列表着色问题实例的难易程度似乎并不完全取决于定量参数,如图的大小、图的密度和颜色列表的大小,而是取决于列表中存在的颜色的分布。[10][11]关键词:列表着色,分支和价格,加权问题。1介绍性图着色问题(GCP)模型的规划问题的范围很广,如时间分配、调度、电子带宽分配和排序等。一些应用对GCP施加了额外的约束,导致已知变量如公平着色、预着色扩展、(γ,μ)-着色和列表着色出现,参见例如[1,2]。实际上,列表着色推广了GCP、预着色和(γ,μ)-着色,并且具有诸如无线网络中的信道定位之类的一些特定应用[3]。在许多实际情况下,颜色具有不同的权重(或成本),并且需要在最小基数的方向上确定最小权重的颜色。特别是,在[4]中,司机工作日的设计1这项工作得到了ANPCyT赠款PICT-2016-0410和PID-UNR ING 538的支持。2电子邮件地址:mlucci@fceia.unr.edu.ar3电子邮件地址:nasini@fceia.unr.edu.ar4电子邮件地址:daniel@fceia.unr.edu.arhttps://doi.org/10.1016/j.entcs.2019.08.0541571-0661/© 2019作者。出版商:Elsevier B.V.这是CC BY许可证(http://creativecommons.org/licenses/by/4.0/)下的开放获取文章。614M. Lucci et al./理论计算机科学电子笔记346(2019)613=Σ+在公共运输公司中,它被建模为最小加权列表着色问题(MWLCP)。设G=(V,E)是一个无向简单图,C是一组颜色。G的着色是一个函数f:V→C,使得对于G的每条边(u,v)f(u)/=f(v)。给定G的一个着色f,j她家C的类颜色,用f−1(j)表示,是由j着色的垂直集v,即f(v)=j。显然,每一种颜色都是一种G的稳定集,因此,任何着色都可以被认为是垂直线到稳定集的划分。用A表示的着色f的活性颜色是这些1。分配给一些顶点,即A. E. {j她家C:f−1(j)/= √}。 GCP由以下各项组成用A的最小基数求G的一个着色。这个最小值叫做G的色度数,用χ(G)表示,并且已知获得这个数对于一般图是NP-难的尽管困难重重,但获得大量应用的具体解决方案的需求推动了GCP几种精确算法的发展:组合分支和绑定算法,如DSATU[5,6]、分支和剪切BC-COL[7]和分支和定价LPCLOR[8,9,10]。在BC-COL的情况下,使用基于经典顶点-颜色赋值变量的整数线性编程(ILP)紧凑公式(GCP-CF,从现在开始)。相反,LPCLOR基于集覆盖ILP公式(GCP-SC),其中每个变量表示G的一个稳定集。由于变量的数量通常在G的大小上是指数的,所以GCP-SC的线性松弛的分辨率由列生成过程来解决。在列表着色中,每个顶点v她家都有一个预分配的列表L(v)C,定义了可以分配给v的颜色。形式上,G的一个列表着色是G的一个着色f,附加条件是f(v)≥L(v)对于所有v≥V。请注意,经典G的着色是其中L(v)=C对于所有v她家V的列表着色。给定一个向量w该书ZC,MWLCP由找到这样一个G的着色列表组成因此,weig htsoftheacti vecolors的总和,即j她家是最小的mum。As颜色G可以被认为是列表着色的特殊情况,MWLCP可以被看作是这是GCP加权版本的一个概括然而,这个加权版本可以很容易地简化为GCP,因为人们可以从C中选择cheapestχ(G)颜色来获得最小权重的颜色。显然,MWLCP在一般图中是NP-硬的,因为它概括了GCP。如何-有史以来,一些已知的结果表明,MWLCP确实比GCP更难。作为第一个评论,不像GCP,它在任何时候都是可行的|C| χ≥(G),MWLCP即使在以下情况下也可能不可行|L(v)|对于所有v,χ ≥(G)。给出了一个众所周知的例子。在图1中,每个顶点的可用颜色都包含在括号中。实际上,询问G有一个列表着色是NP-完备的,即使当被重新限制为列表大小最多为3且G是一个cograph或[11]第11话。相比之下,GCP可以在线性时间内在坐标图和二分图上求解。另一个例子,这些问题在困难的地方是当图形是M. Lucci et al./理论计算机科学电子笔记346(2019)613615我们可以假设G是连通的,C=v她家VL(v)。。{1,2}{1,3}{2.3}{1,2}{1,3}{2.3}图1。 一个不可能的实例按树宽参数化。对于给定的具有固定树宽t的图G,有一个在多项式时间内找到χ(G)的动态编程算法,同时问如果G有一个着色列表是W[1]-Hard[12]。GCP-CP制剂(分别为上述GCP-SC)可以以这样一种方式扩展到MWLCP,即它们在应用于GCP实例时是一致的。在这项工作中,我们提出了这些扩展的ILP公式,分别称为MWLCP-CP和MWLCP-SC,我们开发了一个分支和价格算法,通过MWLCP-SC求解MWLCP,遵循[8]中提供的一些想法。然而,我们不得不考虑一些额外的问题,这些问题是由GCP和MWLCP之间的分歧引起的。在GCP中,每个顶点都可以用C的任何元素着色,并且所有颜色都具有相同的重量,从而使颜色彼此无法区分。显然,MWLCP不满足此属性,这迫使我们考虑MWLCP-SC中每个稳定集和每个颜色的一个变量。相反,我们设计了一种机制来利用颜色之间的可区分性部分满足的那些情况。可行性是另一个问题,如前所述。在第2节中,我们正式介绍了ILP公式MWLCP-CP和MWLCP-SC。在第3节和第4节中,我们解释了定义分支和价格算法的主要组成部分:LP松弛的求解方式、列的生成方式以及节点分支的穿孔方式。在第5节中,进行了计算实验,以评估我们的算法在不同大小和类型的随机实例上的性能最后,在第6节中,得出了一些结论。2MWLCP的ILP配方考虑MWLCP的一个实例,由图G=(V,E)给出,颜色集C其中weig htswj她家Z+对于ea chj她家c W.L.O.GF或eachcolourj,letVj={v她家V:j她家L(v)},GjbeG的导出子图b和Vj,IjbeGj和S(Gj)beteGj的稳定集。第一个公式基于GCP-CF [7]。我们有一个二进制变量x vj,对于每个v她家v她家j家L(v),其中它的值是1 if且仅当f(v)= j,并且二进制variablesyj它的chyj=1ifj是f中的一个acti ve颜色。然后是MWLCP。616M. Lucci et al./理论计算机科学电子笔记346(2019)613ΣSJXVSJSJJJ它可以表述为以下内容:(MWLCP-CF)minwj和jj≥CS.T.jεΣL(v)xvj= 1v她家V(1)xuj+xvj≤yjj她家C,(u,v)她家E(Gj)(2)xvj≤yjj她家C,v她家Ij(3)xvj该书{0,1}v该书{V,j该书{L(v)}并且j她家{0,1}j她家约束条件(1)确保每个顶点都分配了颜色,(2)强制不分配颜色。相邻垂直线的对接收相同的颜色(当使用该颜色时),并且(3)当v在Gj 中是孤立的v 时,控制y j的动作v。第二个ILP模型对应于作为覆盖的颜色的公式。基于GCP-SC的稳定集垂直度。这里,我们有一个二进制变量xj为每个j她家C和每个稳定集S她家S(G j)。注意,对于任何颜色j,它的颜色类是来自G的稳定集,并且不像GCP,不超过一个最大稳定集的Gj可以被封面使用。下面的ILP模型自然是白羊座:minΣwjΣjj她家S(Gj)S.T.jεΣL(v)SΣS(Gj)是的S≥1v她家V(4)SεΣS(Gj)S≤1j她家C(5)SDrew{0,1}jDrewC,SDrewS(G)约束条件(4)表示,对于每个顶点v,至少选择了一个包含v的稳定集,而(5)允许为每个颜色取最多一个稳定集。然而,这个公式并不能恰当地概括GCP-SC,因为GCP的一个实例给出了一个变量比GCP-SC多得多的模型。正如我们在引言中所说的,GCP-SC利用了GCP-SC的优势。颜色之间的可区分性。为了克服这种倒退,我们说如果wj=wk和Gj=Gk , 则 t w ocolors j,k 她家C是不可区分的。 LetCk={j她家C:j,k是不可区分的}和{Ck:k她家K}是CXXXM. Lucci et al./理论计算机科学电子笔记346(2019)613617的一个分区,其中KC。换句话说,每个k她家都是代表C中那些元素的颜色。现在,我们可以利用这些颜色之间的对称性,并允许它们的存在。|C K|G k的稳定集而不是单个1的稳定集。更进一步,618M. Lucci et al./理论计算机科学电子笔记346(2019)613XSVSSSSSKSS。0S\∩S。如果|G K| ≤|CK|如果存在验证此条件的最佳解决方案,则可以消除此约束。现在,MWLCP可以重新制定为:(MWLCP-SC)minΣwkΣkk她家(k)(k)S.T.kΣ她家KSΣS(Gk)是的xk≥1v她家V(6)SεΣS(Gk)x k≤ |C K|k摘自K:|G K| ≥|C K|+1(7)xk她家{0,1}k她家{K,S}S(Gk)因此,对于对应于GCP的实例,我们具有K={1}和C1=C。是的,除 此之外,|C |≥|V(G)|限制(7)不 再 需要,我们的 最 后一次配方变成了与GCP-SC相同的配方。3解决MWLCP-SC的给出一个实例(G,C)。,w,L)的MWLCP,让X={(S,k):S惊呼S(Gk),k惊呼K}MWLCP-SC的线性松弛的变量是xk,其中(S,k)她家其约束条件可以写成Ax≥1,Bx≥ −b,x≥0,其中,对于每个变量x,A中对应的列是S的特征向量,B中的列在对应于k她家K的行中有一个非零项−1。进一步,对于每个k她家,b k= |C K|。注意形式xk≤1的约束条件非负权重(non-negative weights)保证至少有一个最优解请检查这些条件)。ForanyXX,letx(X)bev变量xk的v向量限制于(S,k)她家x和LP(X)b是线性松弛或fMWLCP-SC限制于x(X)。WEfirst给出了一些关于LP松弛解决方案完整性的结果,这些结果将在第4节中使用。引理3.1Letx*beLP(X)的最优解,让X≤{(S,k)她家x:|≥ 2 }。|≥2}. 如果fx*(X′)是int eg r,则LP(X)有一个最优int eger解。Pr或of。考虑X的划分X+=XX0。 明确y,x*(X+)是LP(X+)的最优解。自x*(X)是整数,X−X+的变量设为1。然后,b,并将这些变量的发生率替换为LP(X+)中的1,我们得到一个线性程序LPJ over变量X+\X′,它的c h使得x*(X+\X′)是LPj的最优解。 观察到X + \ X ′中表示b和v变量的稳定集是单态的。M. Lucci et al./理论计算机科学电子笔记346(2019)613619设AJ和BJ是A和B的子矩阵,分别对应于LPJ中的约束(6)和(7)。因为AJ的列是单次稳定集的特征向量,所以它们有一个等于1的正输入。 类似地,BJ的列中最多有一个负项等于-1,这意味着矩阵620M. Lucci et al./理论计算机科学电子笔记346(2019)613˜⊂Σ**SΣLPJ的COE函数是完全单模的。因此,LPJ和LP(X)存在整数最优解Q请注意,当ev eryGj完成时,s表设置一个re单例,X是前一个引理的陈述。然后,我们得到:=≤ in推论3.2如果,对于所有j她家C,G j是一个完备图,那么LP(X)有一个积分最优解。实际上,推论3.2也可以从MWLCP的约简导出为二分图上的最小加权完全匹配问题,如下所述。考虑MWLCP的一个实例(G,C,w,L),使得Gj是所有j她家C的完备图。请注意,每种颜色最多只能分配给一个顶点。那么,我们可以假设,|V(G)|≤C(否则,MWLCP将是不可行的)。 让Z成为一组虚拟元素,就像这样|Z|= |C|-|V(G)|。N或w,考虑从b和V(G)Z和C定义的v分的二分图G,andsu c h,对于allv她家V(G)andj她家C,(v,j)isanedgeofG› ifando nly ifj她家L(v)。 (v,j)iswj的weig h t。 Wealso考虑边(z,j)对所有z她家Z和j她家C与零权重。显然,如果f是G的一个着色列表,则存在一个G的完全映射c,它具有边(v,f(v)),对于所有z她家都是v她家V(G)andedgis(z,j(z)),并且从f中的非活性颜色中提取一些j(z)。这东西的重量完美匹配与着色列表的权重相匹配反过来说,对于G′的任何p效应垫c,edg是(v,j)她家的M对于e v和v她家的V(G)定义了一个与M具有相同权重的G的着色列表。G有一个完美的匹配,如果和只有。如果MWLCP是可行的。在实践中,这个问题可以通过匈牙利算法比通过解决LP松弛更快地得到解决。3.1列生成[编辑]XX,x*(X)b是LP(X)的最优解,而(π*,γ*)b是LP(X)的最优对偶解,其中π和γ是p对应于p的对偶v变量约束条件(6)和(7),分别为 (对于那些k她家这样的K) |G K|≤ |C K|我们假设γ*= 0)。 注意,对于任意(S,k)她家KK。KvεSπv−(wk+γk)。X,x S的降低成本 S =c=我们回忆说,x* 是从x*(X)b和p加上零得到的,即x*(X\X)=0,对于LP(X)是可行的,但不一定是最优的。为了知道这一点,我们必须to decide if there exists(S,k)她家X使得ck>0,或者等价地,求解以下是一个辅助问题:(Aux)(S,k)她家X使得v她家x显然,(Aux)等价于求解,对于每个k她家,Gk上的最大加权稳定集problem(MWSSP),其中weig htπv*对于ea chv她家(Gk)。唤醒MWSSP是NP-硬,枚举例程给出在[9]显示[10]当它被分支和价格算法调用时,它应该是合理快速的。 在addi-M. Lucci et al./理论计算机科学电子笔记346(2019)613621K/该书NPΣJ她家然而,并不总是需要将MWSSP求解为最优解。一个可以停止最优化就像一个权重大于阈值的集合S该书S(Gk)。T=wk +γk*找到了。此外,如果对于某些k = 1K,我们具有Gk=Gl且Tk>Tl,则不需要运行Gl的枚举例程,因为为Gk找到的稳定集可以为Gl重新使用。虽然找到一列对于列生成过程来说已经足够了,但初步实验已经表明,在同一时间合并多个列会减少过程的迭代次数,从而减少整个过程的迭代次数。在我们的实现中,我们搜索(如果存在)每个k她家的一个输入变量。观察到列g生成process需要从一个集合XX开始对于其中chLP(X)是可行的。Werecallthat,unlikeGCP,toknowifaninstanceofMWLCP是可行的是一个完整的问题和它所解决的最佳算法一个列表着色,无论何时存在,都是O(2n)n O(1)。在下面的章节中,我们提出了一个初始化过程。3.2初始化线性松弛度。我们的方法是通过为每个顶点创建一个虚拟颜色来扩展解决方案空间。给出MWLCP的实例(G,C,w,L),我们生成一个扩展实例(G,CJ,wJ,LJ)whereCJ=C{dvv:v摘自V(G)},wjJ=wj对于allj摘自C和wdvv=M对于allv摘自V(G),其中M是一个大数ber(例如M=1+JCWJ )。此外,对于一个v ≥ V(G),LJ(v)=L(v)想尽办法。现在,从实例(G,CJ,wJ,LJ)获得的线性松弛是微不足道的。自xdv以来可行{v} = 1对于所有v她家V(G)是允许我们开始的可行解。我们的专栏世代公关或cess。 也就是说,X={({v},dv):v她家{v}}。预计在优化过程中,将不再使用虚拟颜色(Dummy Colors)。事实上,如果一些虚拟颜色在与扩展实例(G,CJ,wJ,LJ)相关的松弛的最优解中仍然活跃,则(G,C,w,L)是不可能的。初步实验已经揭示,当可以生成后期颜色时,从虚拟颜色开始比可行的初始颜色更好(存在提供列表颜色的启发式算法,例如k-Greedy-List[14])。我们推测其原因可能是由于这些颜色产生的初始列质量很差,这使得LP解算器执行更多的迭代。由于我们的列生成过程嵌入在分支和价格框架工作中,因此我们必须为B B树的每个节点解决的子问题应该对应于MWLCP的新实例。为了实现这一目标,我们需要制定一项强有力的分支规则。在下一节中,我们提出了这样一个规则,将[15]中提出并在[8]中使用的第一个规则改编为GCP。622M. Lucci et al./理论计算机科学电子笔记346(2019)61314一个robust分支规则[8]中给出的规则背后的想法是选择两个不相邻的垂直线u和v。并在满足f(u)=f(v)(both)的情况下将解的空间除以这些子共享相同的颜色)和那些满足f(u)f(v)的其他。寻找最优解后一种情况下的着色等价于在通过将边(u,v)添加到G而获得的图上求解GCP。在前一种情况下,必须通过将垂直u和v折叠成单个1(即,将u连接到每个y)来求解从G获得的图上的GCP。顶点从NG(u)→NG(v)并去掉v,其中NG(x)是开邻G中的x)。我们遵循相同的策略,但附加条件是垂直于U和U。v满足L(u)−L(v)−。 我已经找到了最佳着色列表fof.(G,C,w,L),其中f(u)/=f(v)等价于求解实例的(G1,C,w,L)其中G1=(V(G),E(G){u,v}),在哪里找到最优f其中f(u)=f(v)等价于求解实例( G2,C,w, L2)的MWLCP ,其中G2=G\{v}并且u连接到来自NG(v)的每个顶点,L2(z)=L(z)对于所有z她家V(G2)\{u}并且L2(u)=L(u)L(v)。注意,在上述规则的有限数量的应用中,我们得到所有图Gk都是完整的实例。在这一点上,他们的LP松弛的最佳解决方案是由Corollary 3.2积分。此外,由于遍历得到L2(u)的交集,它很可能到达具有具有单例列表的顶点的实例的子问题。由于强制使用该顶点的唯一可用颜色对该顶点进行着色,因此可以根据以下结果对该实例进行预处理:引理4.1设(G,C,w,L)是MWLCP的一个实例,使得L(u)={j}对于某些u她家V(G)和j她家C。 求解(G,C,w,L)等价于求解一个实例(GJ,C,w,LJ)的MWLCP,其中GJ= G\{u},LJ(z)= L(z)\{j}对于所有z她家N(u),LJ(z)=L(z)对于所有z她家V(GJ)\N(u)。证明。如果fJ是(GJ,C,w,LJ)的最优着色列表,则f(u)=j,f(z)=fJ(z)对于所有z她家V(GJ)是(G,C,w,L)的最优着色列表相反,如果(GJ,C,w,LJ)是不可能的,那么(G,C,w,L)也是不可能的。Q它只剩下指定一个选择垂直u和v的标准,我们在下面的地址。4.1分支变量选择策略[编辑]在[8]中,提出了一个简单但有效的规则。我们用K={1}情况下的公式来简要地解释它(省略了superscripts)。假设x *是x *LP松弛的一个非整数最优解Theauthors first search for最大f r动作变量e,即,最小化的nx*S1|x*S1−2|,andpi cku她家1.既然x*S1她家她家/{0,1}和(6)对u成立,那么就存在另一个S2她家ch,x*S2>0和u她家。 然后,他们搜索第一个顶点v,使得v她家的S1 ΔS2,并且,因为事实上,稳定集不同于其他任何一个,因此v存在,并且它与u不相邻。M. Lucci et al./理论计算机科学电子笔记346(2019)613623S1S2在我们的例子中,我们搜索最 令 人 满 意 的 分数x*k|S1|2和我们选择u她家1。引理3.1保证了这样一个稳定集的存在(否则,解决方案将是完整的)。现在我们需要一对(S2,l)就像S1S2一样,u≥S2,且x*l>0。 如果这样的(S2,l)存在,我们选择v她家。 另一方面,我们选择v≥ S1\{u}。这样,我们可以断言u和v是不相邻的并且令人满意。前提条件L(u)†L(v)/=Ω,因为它们的列表中必须有颜色k或l5计算结果。本节致力于分析所提出的分支和价格算法在随机生成的实例上的性能,其中垂直线的数量为n≥1。{50,60,70}和边概率t和p≥{0}。25、0。50,0。75}。C的基数和颜色在列表中的分布由两个pa-rameterc她家{0}支配。5,1。0、1。5}且q≥{0} 25、0。50,0。75}。 前式用于设置C={1, . . . [CN]。后来,当chw指的是membership-to-listprobability时,是一种颜色j她家属于L(v)的概率,对于每个v。权重设置为所有颜色1个。 随机数是由均匀分布产生的。实验包括比较两种方法,我们称之为CPLEX- CF和BP-SC。在前者中,CPLEX的ILP求解器(具有默认参数)求解MWLCP-CF公式。最后是我们的分支和价格算法,它是用C++手动实现的,并且只使用CPLEX来解决LP松弛。为了加快子问题的生成速度,我们对实例所在的数据结构进行了最小的复制和穿孔更改。这节省了时间,因为不需要从头开始重新计算颜色集或子图Gkamong them的分区。Lemma4.1在此阶段应用。然后,子问题以深度优先搜索的方式得到解决。关于定价例程,我们根据值Tk以递减顺序遍历图Gk,以避免在相同图上 在 另一方面,我们当前的实现没有使用匈牙利算法来进行与Corollary 3.2相关的松弛。此功能将包含在未来的版本中。实验 由配备 AMD Phenom II X4 3.4 GHz (使 用单线程 )、3.6 GB 内存 、Ubuntu 16.04操作系统、GCC 5.4.0和IBM ILOG CPLEX 12.7作为整数和线性编程求解器的台式机进行。对每个求解实例施加1小时的时间限制。[10]结果总结在表1中。在每一行中,报告了使用相同的值组合(n,p,c,q)生成的5个实例的平均值:具有高亮度最佳时间的CPLEX-CF和BP-SC的CPU时间平均值(以秒为单位),以及BP-SC扫描的节点数量平均值在平均值中只考虑在时间限制内求解到最优对于那些5个实例中至少有一个未解决的情况,已解决的实例数以括号报告。如果其中任何一个都未解决,则会显示符号正如我们从表中所看到的,BP-SC实现了卓越的性能,能够解决98%的最优问题(405个实例中的特别是,所有624M. Lucci et al./理论计算机科学电子笔记346(2019)61388.7894.082.3632.6(4)1703.64.330.794.568.5281.7(3)14.759.326.11.21.72.64.619.132.643.034.150.471.35.08.311.8npcQ= 0.25Q= 0.50Q= 0.75SC节点SC时间CF时间SC节点数SC时间CF时间SC节点SC时间CF时间0.5470.30.32338.522.0552.91235.90.251.04755.41.279233.6660.3534.2-1.5881.34.2873.3454.8565.2-0.5460.40.61594.2400.9502.1-500.501.01.5572110.73.62.56.2238638.12.5507.8623.445372.93.5--0.5390.30.5260.527.0160.6-0.751.0220.20.4230.653.1130.8-1.5300.40.8190.764.1151.3-0.51071.40.82308.6106.0895143.7-0.251.062714.18.0957.1789.918428.6-1.52618.730.1631102.3-726177.6-0.5430.71.61324.9596.5(2)48749.2-600.501.01.52491135.53.425.934.3711214.110.9--45740868.686.1--0.5510.60.9331.31686.6(3)352.3-0.751.0430.83.1341.8-403.9-1.5320.82.9452.5-334.7-0.25700.500.750.51.01.50.51.01.50.51.01.58467266948145231506661596477223.638831671853233320015066840521154.8(3)--------7195101166153161454546表1随机图的结果(每行平均5个实例具有50和60个垂直点的实例可以在几分钟内求解。当垂直线的数量增加到70并考虑0.5或0.75的边缘概率(中到高密度)时,观察到相同的行为。相比之下,边缘概率为0.25(低密度)的实例有时更难解决,除非成员名单的概率很高。请注意,已探索节点的数量很低,指出线性松弛提供了紧密的边界,节点选择策略足够好,但每个松弛的解决方案也非常耗时。[10]关于CPLEX-CF,我们注意到它在时间限制内解决了一半的实例(405个实例中的 202 个 ) 。 这 个 公 式 的 缺 点 之 一 是 LP 松 弛 的 值 所 提 供 的 弱 下 限 ( weaklowerbound)。事实上,BP-SC的LP松弛比CPLEX-CF的LP松弛大174%(平均),并且该间隙被强调为在任何参数(n、p、c或q)下实例增长的大小。在n =70,p = 0的实例中达到峰值。75,c = 1。5和q = 0。75其中BP-SC的LP松弛度大604%。虽然CPLEX-CF在5%的病例中优于BP-SC,但这些病例通常具有低密度图表和颜色量较小的列表,使得MWLCP- CF在变量和约束条件的数量方面更小。在BP-SC的情况下,图的密度越低,MWSSP在图Gk(其倾向于稀疏)上的分辨率越高。最后但并非最不重要的是,这两种方法不仅在垂直度和密度变化时,而且在垂直度和密度变化时,都明显地干扰了性能。55.8590.0(2)230.5(3)188.514.911.03.23.34.9M. Lucci et al./理论计算机科学电子笔记346(2019)613625颜色列表的结构的一部分。在BP-SC的情况下,这种行为似乎是不可预测的。即使我们设置了垂直度的数量、边缘概率和会员入职概率,性能也不会随着颜色数量的增加而变得更差。6结论在本文中,我们提出了一个分支和价格算法来解决列表着色问题的加权版本,该算法有许多应用,并推广到其他几个着色问题。为了实现这一点,我们提出了一个列生成过程和一个基于GCP[8]中给出的健壮分支方案。特别是,当我们限制来自GCP的实例时,我们的方法就像LPCOLOR一样。然而,其他方面也应该被考虑在内,比如颜色之间的可区分性和缺乏可区分性,这是一个很大的问题。就我们所关心的,这是针对这个问题的第一个基于ILP的精确算法。计算实验表明,我们的算法具有显著的性能,能够在多达70个垂直度和1小时的时间限制内解决最优随机生成的实例。我们的结果还表明,实例的难易程度似乎不仅取决于生成参数(n、p、c和q),而且还取决于列表中存在的颜色分布。在这方面,我们相信,进一步的研究仍有待完成。特别地,应该研究Gk图的结构,即大小、密度和重叠(它们彼此共享的垂直线的数量),如何影响分支和价格算法的性能。[10][11] 更好地理解困难的实例可以帮助更好地检测问题。在我们的算法中考虑机会。在未来的工作中,我们计划评估我们的算法在其他类型实例上的性能例如,通过向颜色添加不同的权重、改变不可区分颜色的数量、使用来自应用程序的实例(请参见E.G. [4])和其他着色问题(例如,预着色扩展,(γ,μ)-着色)或通过创建基准图的实例,如来自COLORLIB(DIMACS)的那些。参考文献[1] Kubale,M.,图着色,美国数学学会(2004)。[2] 博诺莫,F. G. 杜兰,J. Marenco,《探索颜色和列表颜色中的模糊性》,Ann.Oper. 第169(2009)号决议,第3[3] 王,W.,和X. Liu,开放频谱无线网络的基于列表着色的信道分配,IEEE第62届车载技术会议,达拉斯,德克萨斯州,美国(2005),690[4] Lucci,M.,G. 纳西尼和D. Sever n,通过Graph列表着色模型规划公交车司机的工作日,电子杂志SADIO17(2018),77[5] Br'elaz,D. 新的方法或ds颜色的Verti ces的一个G raph,Com mun。 CM22(1979),251-256。[6] 圣塞贡多,p。一种新的基于DSATU的精确顶点着色算法,Comp.歌剧院。Res. 39(2012),1724626M. Lucci et al./理论计算机科学电子笔记346(2019)613[7] M'endez-D'az,I. 和P。Zabala,一种用于g raphc着色的切割平面算法,Discr. 应用程序。 马特。156(2008年),第159[8] Mehrotra,A.和M。Trick,图着色的列生成方法,INFORMS J.Comput. 8(1996),第331[9] 赫尔德,S.,E. 休厄尔和W。库克,图形着色的安全下限,Lect.笔记本电脑。Sc.6655(2011),第261-273页。[10] Malaguti,E. M. Monaci和P. Toth,顶点着色问题的精确方法,Discr. 最佳。8(2011),第174[11] Golovach,P.,M.约翰逊,D. Paulusma,and J. Song,A Survey on the Computational Complexity ofColoring Graphs with Forbidden Subgraphs,J. Graph Theory84(2017),331[12] Cygan,M.F. Fomin,L.Kowalik,D.Lokshtanov,D.马克思,M.Pilipczuk,M.Pilipczuk,和S.Saurabh,参数化算法,Springer国际出版社(2015年)。[13] Bjorklund,A. T. Husfeldt和Mikko Koivisto,通过包含-排除进行集划分,SIAM期刊计算。39(2009),第546[14] Achlioptas,D.,和M。Molloy,随机图上列表着色算法的分析,第38届计算机科学基础年度研讨会,迈阿密,佛罗里达州,美国(1997),204[15] Zykov,A.A.、论线性复形的某些性质,Matematicheskij Sbornik24(1949),163
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 保险服务门店新年工作计划PPT.pptx
- 车辆安全工作计划PPT.pptx
- ipqc工作总结PPT.pptx
- 车间员工上半年工作总结PPT.pptx
- 保险公司员工的工作总结PPT.pptx
- 报价工作总结PPT.pptx
- 冲压车间实习工作总结PPT.pptx
- ktv周工作总结PPT.pptx
- 保育院总务工作计划PPT.pptx
- xx年度现代教育技术工作总结PPT.pptx
- 出纳的年终总结PPT.pptx
- 贝贝班班级工作计划PPT.pptx
- 变电值班员技术个人工作总结PPT.pptx
- 大学生读书活动策划书PPT.pptx
- 财务出纳月工作总结PPT.pptx
- 大学生“三支一扶”服务期满工作总结(2)PPT.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功