加权非正常染色的理论计算机科学电子笔记322 (2016) 181-195

NP可在www.sciencedirect.com在线获取理论计算机科学电子笔记322（2016）181-195www.elsevier.com/locate/entcs加权非正常染色的Bjarki Agust Gudmundsson1 托马斯·肯·马格努森2Bjorn Orri Saemundsson3冰岛雷克雅未克大学计算机科学学院ICE-TCS摘要研究了亏色的一个推广&加权非正常染色问题。我们提出了一些硬度的结果，特别是我们表明，加权不当染色是不固定参数的路径宽度参数化时，易于处理。将亏染色的界推广到加权非正常染色，并给出了加权非正常染色的一个关于边权和的界。最后，我们给出了固定参数算法加权不当染色时，参数化的树宽和最大程度和参数化的树宽和精度的边缘权重。特别地，我们得到了有界度区间图的加权非正常染色的线性时间算法关键词：图着色，非正常着色，缺陷着色，加权非正常着色，着色界，固定参数算法1引言图着色是数学和计算机科学的经典课题，有着许多实际应用。 它是卡普的21个原始完整的问题之一lems。图着色的许多推广，如亏损着色，已被研究，但大多数适用于无向图。本文研究了加权非正常染色，它是加权有向图染色的一个推广。加权不当着色一直没有得到太多的关注，直到最近在无线网络的上下文中。在无线网络的一些模型中，例如SINR模型，一个无线链路上的通信可能干扰其他无线链路上的通信。这种干扰可能因链路而异，并取决于1电子邮件：bjarkig12@ru.is2电子邮件：tomasm12@ru.is3电子邮件：bjorn12@ru.ishttp://dx.doi.org/10.1016/j.entcs.2016.03.0131571-0661/© 2016由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。182B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）1810。90。30。50。20。20。60。70。7∈∈≤联系我们G=（ V，E，w）w：E→[0，1]Σ信号强度和周围环境的其他变量。此外，扰动不需要是对称的。在这样的网络中，通信的调度可以被建模为加权的不适当着色，这就是泛化的起源。本文给出了加权非正常染色的一些新的界、固定参数算法和困难性结果，其中一些结果是亏损染色已有结果的推广.1.1分类设G=（V，E）是一个无向图.对于顶点v，设d（v）表示v在G中的度，dS（v）表示v在由子集S导出的子图中的度V. A k-染色c：V1、......、K是G的顶点的一个划分将V设置为k个顶点不相交的子集，并且c[v]表示具有颜色c（v）的顶点的集合。一个k-染色c是d-亏损的，如果对每个v V，dc[v]（v）d.一个d-亏损k-染色也称为（k，d）-亏损染色. 注意，普通染色是亏染色的一个特例，其中d=0，所以亏染色是普通染色的一个适当推广。设是一个加权有向图，其中是一个相关的权函数。对于顶点v∈V，设d−（v）=（u，v）∈Ew（u，v）表示它的加权入度，d−S（v）表示v在由子集S∈V导出的子图中的加权入度.令Δ−表示任何加权入度的最大值定义1.1一个加权有向图G=（V，E，w）的k -染色c是一个加权imp ro perk-染色if， 其中eachvertexv∈V，d-c[v]（v）<1. 加权改进色数χw（G）是使G有一个加权改进色数的最小数k关于权函数w的不适当k-着色。0。七点零分7Fig. 1.一个有效的加权不正确染色的图的左边。右边的图有一个无效的着色，因为左上角的顶点与相同颜色的邻居的入度为1现在请注意，加权非正常染色是亏损染色的推广，并且通过推广是普通染色的推广，如下面的引理所捕获的。引理1.2亏（k，d）-染色可在多项式时间内化为加权非正常k-染色.证据设G是一个无向图。在G的一个有效亏（k，d）-染色中，任意顶点v∈V（G）至多有d个相邻的同色顶点. 设GJ是将E（G）的每一条边{u，v}替换为两条而0。90。30。50。20。20。60。70。7B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181183d+1∈--∈⊆c[v]||−d+1c[v]d+1有向边（u，v）和（v，u），权重为1。显然，任何顶点vJV（GJ）不能有多于d个相邻的同色顶点，因为这样我们就有d−′（vJ）≥ d+1= 1。然而，vJ可以有多达d个相同的相邻顶点，因为这产生d−′（vJ）≤d<1。 因此，任何有效的加权不当k-c GJ的一个有效的亏（k，d）-染色也是G的一个有效的亏（k，d）-染色，GJ的任何无效的加权非正常k-染色也是G的一个无效的亏（k，d）-染色.时间复杂度为O（|E（G）|），并且因此是多项式时间缩减。Q由于这种约简不会改变图的底层结构，而只是增加了权重，因此我们得到以下推论。推论1.3任何特定图类的亏（k，d）-染色都有多项式时间减少到同类图类的加权不当k-染色。最后，我们定义一个树分解如下：定义1.4图G=（V，E）的树分解是一对（X，T），其中X=X1，.，X n是V的子集的集合，T是一棵树，它的顶点是X中的子集，我们称之为超顶点。此外，必须保持以下属性：(i) 如果v∈V，则存在子集Xi使得v ∈Xi，(ii) 如果（u，v）∈E，则存在子集Xi，使得u ∈Xi且v ∈Xi，且(iii) 如果v V和XvX是包含v的子集的集合，则Xv形成T的连通子树。树分解（X，T）的宽度是maxiX i1。图G的树宽是图G的任意树分解的最小宽度。路径分解是树分解（X，T），其中T是路径图.图G的路宽是图G的任意路分解的最小宽度。最后，路径和树分解可以通过使用底层图（即通过将有向边视为无向边）扩展到有向图以前的工作亏损着色和相关的t-不当着色首先由Andrews和Jacobsen [1]，Harary和Frank [14]以及Cowen等人提出。[10 ]第10段。图嵌入表面的主要焦点是Cowen等人。[10]和Cowen，Goddard和Jeserum [9]，他们刻画了所有的（k，d）使得平面图是d-亏k-可染的，并给出了高阶亏格曲面的结果。Frick和Henning [12]给出了随机图的亏色数的极值结果，Kang和McDiarmid [17]证明了随机图的亏色数增长的界除了顶点的度之外，其他的性质也被研究过，Frick [11]给出了一个很好的调查。第一个提出这种无向图的边加权变化的是Hoefer，Kesselheim 和Vöcking[16]。Araujo等人[3]问题在于184B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181NP一个可变的阈值的程度上的一个顶点就其着色和explored对偶问题的finding这样一个阈值，除了产生结果的各种网格图。类似的信道分配问题也被考虑并建模为顶点加权图上的着色[6]。Tamura等人。[22]和Archetti等人。[4]提出了SINR模型系统的无线调度的明确公式，作为定向加权不适当着色，并且大多数工作都假设了干扰的几何限制，同时已经发表了一些一般性结果最近Halldórsson和Bang-Jensen [5]给出了本质上有界χw（G）≤[2Δ−+1.2硬度建立了有关着色缺陷的一些硬度结果。Cowen和Jeserum [9]证明了（2，d）-亏损染色对d≥1是NP-完全的，甚至对平面图也是NP -完全的，而（3，1）-亏损染色对平面图也是NP-完全的.进一步证明了对任意k≥3，d≥0，（k，d）-亏损染色是NP-完全的.这些结果可以推广到加权非正常染色，如我们在下面的推论中所示。推论2.1当k ≥ 2时，加权非正常k-染色是NP-完全的.证据 这是从引理1.2和亏（k，d）-着色是NP-完全，其中k= 2且d≥1，以及k≥3且d≥0。Q注意，由于2-着色有一个简单的多项式时间算法，所以亏2-着色和加权非正常2-着色是-完全的有点令人惊讶。推论2.2当k ∈ { 2，3 }时，平面图的加权非正常k-染色是NP-完全的.证据这是由推论1.3和当d≥1时平面图的（2，d）-亏损染色是NP-完全的事实以及平面图的（3，1）-亏损染色是NP-完全的事实Q由于任何平面图都是4-可着色的[2]，这是比加权不当4-可着色更严格的要求，并且由于1-可着色是平凡的，这与推论2.2一起给出了平面图的加权不当着色的完全硬度结果。现在考虑一个图G，假设我们给这个图添加任意数量的0-权边来生成一个新的图GJ。由于这些0-权边没有施加新的限制，很明显，G是k-可着色的当且仅当GJ是k-可着色的。事实上，我们可以添加0-权重边，直到图是完整的，而不添加任何限制，因此，在某种意义上，我们总是可以假设这个图是完备的。这一观察导致了下面的引理。B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181185Np∈∈×∈NPNPNPG--{A，v}{v，B}w=2x/X − x/|S|我我我--引理2.3设G是一个图族，使得对于每个n，Kn∈ G. 则G 的加权非正常k-染色是NP-完全的.证据 我们通过减少一般的加权不当k-着色来证明这一点，- 完全由推论2.1，加权不当k-染色。取任意一个加权有向图G=（V，E，w）。通过在没有边连接的顶点对之间添加0-权边，从G创建完全加权有向图GJinG.显然G是k-可染的当且仅当GJ是k-可染的。由于GJ是一个完全图，我们看到GJ∈G，从而得出约简。Q特别是，这个引理意味着区间图的加权不当染色的-完全性，CnKt，和第k次权力的道路和循环，其中t和k是无界的。稍后我们将给出这些和其他图类的固定参数算法。这个引理可以进一步推广，注意到具有0-权重边的顶点也可以添加到图中而不添加任何限制，因此可以使用具有足够大的完全子图的图来代替完全图。定理2.4路宽有界的图的加权非正常染色是-完全的.证据 给定一个多重集S=x1，...，正整数x n，划分问题的任务是决定S是否可以划分为两个集合S1，S2，使得xS1x=xS2x. 通过将划分问题转化为加权非正常染色问题，证明了路宽有界的图的加权非正常染色是完全的有界路宽图我们构造一个无向图G=（V，E），使得对于每个整数x iS， 我们给V加上一个对应的顶点v i，以及两个额外的顶点A和B。我们添加一条无向边A，B，权重为1，对于每个顶点vi，我们添加两条无向边和，其中X=<$x∈Sx。 该图如图2所示。图二、子集和建模为加权不当着色。我们证明了S可划分为S1和S2的充要条件是G存在一个有效的加权非正常2-染色。给定一个将S划分为S1，S2的划分，我们将颜色1分配给对应于整数xi∈S1的每个顶点vi，相反，我们将颜色2分配给对应于整数xi∈S2的每个顶点。此外，我们将1赋给A，将2赋给B。为一w1w2wn一对一对二。 .vnw1w2wnB186B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181-||NPc[A]我 X我|S|X·2−|S||S|我2|S|2我|S|2|S|210。510。5110。5111110。50。51每个v i我们有dc[vi]（v i）=w i=2x i/X i/ S <1作为一个单一的整数不能超过一半的整数总和，否则分区将是无效的。对于A，d（A）=10w=2xi∈S1x−|S1|= 2Xxi∈S1|= 1−|S1 |2001年。|ϵ <1.同样的论点也适用于B。因此，该划分产生G的有效的加权非正常2-染色。给定G的一个有效的加权非正常染色，设S1是与A属于同一色类的所有顶点，S2是与B属于同一色类的所有顶点.然后x=xi∈S1X.W+=XW+|S1|X≤X。1−+|S1|X≤X，这同样适用于S2。对于S1，S2，我们得到：x≤X根据定义，x∈S1x+xx∈S2I2x=X，因此等式成立。...图3.第三章。从划分问题的一个实例构造的图的路径分解图G的路径宽度为2，这可以通过最优路径分解来看出图3所示的G。 利用划分问题是完全的这一事实，”[15]这是一个证明。Q3界限禁止权为1的边会对赋权图的着色产生影响图4中的3-正则图具有加权不正确色数3，即使每个顶点都有一个权重小于1的关联边。然而，没有权为1的边的3-正则图的权不当色数至多为2，如以下引理所示。图四、一个3-正则图，其中每个顶点都有一条权小于1的关联边。引理3.1如果G=（ V，E，w）是一个加权图，使得对于每个e∈ E且每个顶点至多有3个邻点，则χ w（G）≤ 2.A，v1， BA，v2， BA，vn，Bvi∈c[A]我vi∈c[A]B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181187| |联系我们，−，w最小值、、、w最小值，−，−w最大w最大w最大≤χ w（G）.+1最少1个χw（ G）≤1w最大+1。+1⎢+1证据 从G的任意2-着色c：V1，2开始. 当我们有一些顶点至少有两个相同颜色的邻居时，选择这样一个顶点v，并将v的颜色改为相反的颜色。该步骤将单色边缘的数量减少至少1，并且由于开始时最多有E个单色边缘，因此该过程在有限数量的步骤后停止。当过程停止时，每个顶点最多有一个入射单色边，并且当权重小于1时，顶点关于其颜色的度小于1。Q我们可以将Lovász [20]的结果推广到我们的问题。显然χ（G）（d+1）≤χ d（G）[18]，其中χ d（G）是d-亏色数. 类似结果对于无向加权不适当着色成立引理3.2若G=（ V，E，w）是一个无向赋权图，其最小正边权为 wmin，则中国（G）最少1个是的。通过对e∈E中的所有边进行恢复，使w（e） =0，从而得到了W e星t。给我，给我，如果G的任意点都是用χw（G）色着色的，则G的每个顶点至多有−邻居有相同的颜色。因此，根据布鲁克斯因此，χ（G）≤.，1−n，+1n× w（G），得到引理。Q定理3.3若G=（ V，E，w）是一个加权有向图，其中基图的最大边权和最大边权，则⎢⎡Δˆ⎤⎥证据 构造了一个加权无向图GJ=（VJ，EJ={{u，v}：（u，v）∈Eor（v，u）∈E}，WJ），其中WJ（e）=wmax，e∈EJ. 显然，当增加g条边和增加宽度时，χw（G）≤χw′（GJ）。注意eachv∈VJ可以有ave至多最大1mW在一个有效的加权不适当的着色相同颜色的邻居。让k=，Δk/，1−k+1，，+ 1，并且从G j的一个nyk-染色开始.假设存在一个顶点v，它有超过1−1个相同颜色的邻居。首先假设v在每一个颜色类别中都有超过1−1个邻居。但后来.，1−1，MaxΣ⎡⎢ΔˆWMax⎥⎤ˆΔˆWMax+1个dG′（ v）≥w+1，1−，的188B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181≥Δ+，1−B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181189、、、w最大、、、w最大| |w最大、、、w最大[2014 -05-23]≤，，nx（G）≤2 2W+1。W联系我们是的。 设t表示G的顶点vo∈G且d−（v）≥W/2的个数. 如果你不介意，这一点与Δθ是底层图的最大度这一事实相矛盾ofG.因此，存在一个颜色类，其中v最多有1−є邻居和我们将改变v的颜色为任何这样的颜色类的颜色我们可以重复前面的过程，当存在一个顶点，1-1个相同颜色的邻居。现在考虑图中的单色边，开始时最多为E。在这个过程中，每次我们改变顶点的颜色，单色边的数量至少减少一个. 因此，这个过程必须终止，此时每个顶点最多有1−є相同颜色的邻居，所以我们有一个有效的k染色。Q由于前面的证明是构造性的，我们得到以下推论：推论3.4对于加权有向图G =（V，E，w），最大重量Wmax和最大d eg reeΔmax， aweighte dimproper.，Δ/，1−在O.Δˆ|E|休息时间。Halldórsson和Bang-Jensen [5]证明了χ w（G）2Δ−1+1的最大加权入度的本质紧界.在下面的定理中使用这个界限来给出边权重之和的界限。定理3.5若G=（V，E，w）是一个权eddigraph，且W=e∈Ew（e），则当这些顶点的总深度满足t·W/2≤W时，我们得到t≤2W时的结果.设GJ是入度至少为W/2。 由[5]图hG GJ的其余部分有色数χw（G GJ），2W/2 +1，=，n =2W+1，. 通过用，，<$2W，+，<$2W+1，色，以及定理Q4固定参数算法当用树宽参数化时，普通图着色和缺陷着色都是固定参数易处理的[19，21]。因此，很自然地要问，加权的不适当着色是否定理2.4表明情况并非如此。...v. ......你好。图五、一个加权有向图及其树分解。u0。9...v0。9Wv，uv，w190B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181----图5显示了一个图的一小部分（左边），以及这些顶点之间的关系在同一个图的树分解中可能是什么样子（右边）。经典的固定参数算法通常会在某个点访问对应于子集v，u的顶点，并为v和u选择颜色。然后，它将继续向下进行树分解，可能访问多个顶点，然后最终到达与子集v，w对应的顶点。此时，需要给w分配某种颜色，很明显，它不能与分配给v的颜色相同。 另一方面，如果这是加权的不正确着色，那么将v这取决于v的哪些邻居具有与v相同的颜色。在这个例子中，它取决于u的颜色，可能还有其他顶点。这表明，顶点的有效颜色可能取决于多个决策，这些决策不是树分解中最接近的祖先的局部决策，这可能会给一些直觉，说明为什么加权不正确着色在仅由树宽参数化时不是固定参数易处理的然而，我们现在证明，当用树宽参数化时，加权不当着色是固定参数易处理的，并且图或边权重的精度作为实现这一目标的第一步，我们提出以下事实。事实4.1 [8，定理6]树宽为k的图G的色数至多为k+1。由于普通染色比加权非正常染色有更严格的要求，因此树宽为k的图G的加权非正常色数也至多为k+1。以下算法对最优树分解进行操作，其可以[7]在线性时间（树宽有界时）内，由Bodlaender [7]构建4.1有界树宽与有界最大入度如果我们另外限制图的最大未加权入度，那么就可以跟踪树分解中给定超级顶点内所有顶点及其所有内邻居的颜色，这正是检查该超级顶点内给定顶点的着色限制是否满足所需的信息。现在考虑任意树宽有界且最大入度有界的加权有向图G=（V，E，w）。算法1是对经典的固定参数算法的改进，用于普通图的着色.它还跟踪被着色的顶点的内邻居的颜色，以便能够检查权重限制。调用COLOR（Xi，c<$）返回最小值lsuch，使得由以X i为根的子树中的超顶点所包含的顶点诱导的子图相对于部分着色c <$是l-可着色的。 相反，查询CCOLOR尝试顶点及其邻居的所有可能的着色c，对那些已经用着色c′着色的顶点使用相同的颜色。然后它递归地调用自己B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181191←←←来回答更多的子问题。算法1有界树宽和有界最大入度图的固定参数算法。1：函数CCOLOR（Xi，c<$）2：开始3：设Xp是Xi在T中的父集合，或者是空集，如果Xi是根4：设Vi是Xi中的顶点及其所有内邻点的集合，设Vp对于Xp，5：χ←+∞6：对于each ch着色c：Vi→ {1， . ， k+1}，其中c（v）=c<$（v），对于v∈Vi<$Vpdo7：如果d−c[v]（v）1，对于eachv∈Xi，则8：xjC使用的颜色的最高索引9：对于Xi的每个子元素Xj，10：χJmax（χJ，COLOR（Xj，c））11：结束12：χmin（χ，χJ）13：如果结束14：结束15：返回x16：结束十七： 构造G的树分解（X，T），其宽度不超过k18：在超级顶点X1处根树T19：returnCOLOR（X1，）为了证明这个算法的正确性，基本上有三个属性需要证明：• 对顶点的颜色分配是一致的，即，恰好一种颜色被分配给给定顶点，并且该颜色在算法的整个持续时间内被使用，• 算法发现的任何着色都是有效的，并且• 任何有效的着色都可以由算法发现下面两个引理在本文[13]的扩展版附录A的A.1节中得到了证明。引理A.4 [13]算法1发现的任何着色都是有效的。引理A.5 [13]任何至多k + 1种颜色的有效着色都可以通过算法1发现。这些引理给出了下面的定理。定理4.2当以树宽和最大入度为参数时，加权非正常染色是固定参数易处理的。192B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181.Σ.Σ.Σ.Σ.ΣNP×−证据引理A.4和A.5表明，算法1发现的着色恰好是使用至多k+ 1种颜色的有效着色。特别地，由于事实4.1的加权不当色数至多为k+1，因此它将发现具有最小颜色数的所有着色当该算法返回任意着色中的最小颜色数时，它将返回输入图G的加权不当色数。算法1具有指数时间复杂度，因为它本质上是一个回溯算法，探索最多k+1种颜色的所有有效着色。现在请注意，CCOLOR函数的结果仅取决于其输入参数的值。还请注意，递归调用的调用层次结构是非循环的。因此，可以使用动态编程有效地计算这些函数调用的结果。也就是说，通过计算所有可能的输入参数的函数调用结果，存储所有结果，然后重用存储的结果在需要的时候。 假设n=|V（G）|，ke为树宽，Δk−表示最大值不考虑G. 因为有（k+1）（k+1）Δk − 一个从（k+1）Δ−元素的集合到一个k+1元素的集合的p可能映射s，有On（k+1）（k+1）Δ−C颜色函数的可能输入参数。因为它们中的每一个的结果可以在On（k+1）（k+1）Δk - 1 中 计 算 。时间，这给了我们总的时间复杂度On2（k+1）2（k+1）Δ− . 虽然对于这个结果是不必要的，但是注意到each超级顶点实际上只被引用了两次，这将时间复杂度降低到On（k+1）2（k+1）Δn - . 这个时间复杂性以及al-taxm的正确性证明了当用树宽和最大入度参数化时，加权不当着色是固定参数易处理的。Q该算法具有存储复杂度yOn（k+1）（k+1）Δn - . 还可能感兴趣的是，使用常见的动态编程技术，可以构造最优着色，或者对最优着色的数量进行计数。有界树宽和有界最大度的图很多，该算法应用于这些图时是线性的。这包括有界度区间图，Cn Kt，其中t是有界的，以及k次幂的路径和循环，其中k是有界的。记住，用引理2.3对这些图类的无界版本加权不适当着色是完全的。4.2有界树宽和有界精度权重另一种可能性是额外限制图中权重的精度。考虑一次为一个顶点指定颜色的过程。最初，当没有顶点被着色时，所有顶点从相同颜色的顶点具有0的加权入度，并且允许具有1/4的相同颜色的顶点的附加加权入度。我们称之为顶点的预算。随着更多的顶点被分配颜色，给定顶点的预算逐渐减少。如果权重具有有限的精度，则可以在这样的过程中跟踪预算现在考虑任意有界树宽为k的加权有向图G=（V，E，w）B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181193以及具有B比特的有界精度的边缘权重。设R表示b位固定精度实数的集合。算法2类似于算法1，是经典的固定参数算法的一种适应，用于普通图着色，但它不是邻居的着色，而是跟踪顶点预算来检查权重限制。calltoCOLOR（Xi，c）返回一个最小子图，使得由以Xi为根的子树中的超顶点所包含的顶点导出的子图是l-可着色的，条件是：• 由参数c′给出的部分着色是在Xi（可以与Xi共享一些顶点），以及• 第二个参数rgi表示X i的剩余预算。为了回答这个问题，COLOR尝试了Xi中顶点的所有可能的颜色c同时保持由yc′给出的颜色。 然而，它不能直接调用自己递归地解决进一步的子问题。原因是给定顶点的预算在子超顶点之间不是独立的。为了打破这种依赖性，Dist ribute函数将给定顶点的预算分布在子超级顶点之间。这是通过递归地遍历超顶点Xp的所有子超顶点并决定在以第i个子顶点为根的子树中可以花费多少预算来完成的。然后用这个预算，r，在第i个孩子上调用C，OLOR，来解决进一步的子问题.为了论证这个算法的正确性，需要展示与算法1相同的三个下面两个引理在本文[13]的扩展版附录A的A.2节中得到了证明。引理A.8 [13]算法2发现的任何着色都是有效的。引理A.9 [13]任何至多k + 1种颜色的有效着色都可以通过算法2发现。这些引理给出了下面的定理。定理4.3当以树宽和权的精度为参数时，加权非正常染色是固定参数易处理的。证据引理A.8和A.9表明，算法2发现的着色恰好是使用至多k+ 1种颜色的有效着色。特别地，由于事实4.1的加权不当色数至多为k+1，因此它将发现具有最小颜色数的所有着色当该算法返回任意着色中的最小颜色数时，它将返回输入图G的加权不当色数。算法2具有指数时间复杂度，因为它本质上是一个回溯算法，探索最多k+1种颜色的所有有效着色。现在请注意，DistR ibute和COLOR函数的结果仅取决于其输入参数的值。还请注意，递归194B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181J←←−←≥∈||算法2有界树宽和有界精度权重的图的固定参数算法。1：函数DistRibute（Xp，c<$，r<$，i）2：开始3：如果Xp有少于i个孩子，则4：返回05：其他6：设Xi是Xp的第i个子元素7：χ←+∞8：对于每个可能的r：Xp→R，其中0≤r（v）≤r<$（v），9：χJ←max（DistRibute（Xp，c<$，（r<$−r），i+1），COLOR（Xi，c<$，r））10：xmin（x，x）11：结束12：返回x13：如果结束14：结束15：函数COLOR（Xi，c<$，r<$）16：开始17：设Xp是Xi在T中的父集合，或者如果Xi是根则18：χ←+∞19：对于each ch着色c：Vi→ {1， . ， k+1}，其中c（v）=c<$（v）forv∈Vi<$Vpdo20：设r：Vi→Rsuch，如果v∈ Vp且r（v）=1−<$，则r （v）=r<$（v），否则21：对于每个（u，v）∈E（G）do22：如果{u，v}<$Xi且（u/∈Xp或v/∈Xp），则23：r（v）r（v）w（u，v）24：如果结束25：结束26：如果对于每个vXi，r（v）0，则27：χmin（χ，DistR ibute（Xi，c，r，1））28：如果结束29：结束30：返回x31：结束三十二： 构造G的树分解（X，T），其宽度不超过k33：在超级顶点X1处根树T34：returnCOLOR（X1，，）呼叫是非循环的。因此，可以使用动态编程有效地计算这些函数调用的结果。也就是说，通过计算所有可能的输入参数的函数调用的结果，存储所有结果，然后在需要时重新使用存储的结果。设n=V（G），k为树宽，b是权重的精度（即用于表示它们的比特数）。因为从一个k+ 1个元素的集合到一个集合有（k+ 1）k+1个B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181195.Σ.Σ在k+1个元素中，有O. n2（k+1）k+12b（k+1）个可能的输入参数到功能 其中每一个的结果都可以计算出来，O.2b（k+1）阶时间。 同样地，我们可以看到有O。n（k+1）k+12b（k+1）pos-可以在O n2（k+ 1）k+1次内计算。这就给出了总时间复杂度On2（k+1）k+122b（k+1）+n3（k+1）2（k+1）2b（k+1）。 这个时间复杂度以及算法的正确性证明了加权非正常着色是固定参数的，当用树宽和权重精度参数化时，是容易处理的。Q5结论本文定义了加权非正常染色问题，并给出了它的一些困难性结果，特别是证明了当路径宽度固定时，加权非正常染色是不固定参数易处理的.我们将亏色的一些界推广到加权非正常染色，并利用Halldórsson和Bang-Jensen [5]的界得到了加权非正常染色的一个关于边权和的界由于这个界并不紧，所以找到一个关于边权重之和的紧界会很有趣我们还证明了边权严格小于1的3-正则图是2-可着色的，并且当每个顶点至多有两条关联边权为1时，两种颜色可能是不充分的。找到一个3-正则图是2-可着色的关于边权的充分必要条件是很有趣的。特别地，我们猜想至多有一条关联权为1的边的次立方图是2-可着色的。当树宽和最大度固定或树宽和边权值精度固定时，我们给出了加权非正常着色的固定参数算法这些算法也意味着一个线性时间算法的某些图形类，如区间图有界度。将圆化边权重与用于有界树宽和有界精度权重的固定参数算法相结合，本文介绍了我们在计算机科学学士学位研究的最终项目的结果，我们要感谢我们的导师，Magnús Már Halldórsson，他的指导，建议和有用的提示。我们也要感谢Henning Schlfarsson的审查。引用[1] Andrews，J. A. 和M.S. Jacobson，关于色数的一个推广，Congressus Numerantium47（1985），pp. 33比48[2] 阿 佩 尔 ， K 。 和 W. Haken ， Every planar map is four colorable ， Mathematical Solitaires Games（1980）. 一百四十五[3] Araujo，J.，J. - C. Bermond，F.Giroire，F.Havet，D.Mazauric和R.Modrzebrski，加权不当着色 ， 在 ： C 。 Iliopoulos 和 W. Smyth ， editors ， Combinatorial Algorithms ， Lecture Notes inComputer Science7056，Springer Berlin Heidelberg，2011. 1比18可输入参数到C色函数和每个函数的结果196B.A. Gudmundsson等人/理论计算机科学电子笔记322（2016）181[4] 阿尔凯蒂角，N. Bianchessi，A.Hertz，A.Colombet和F.Gagnon，蜂窝信道分配的定向加权不当着色，离散应用数学182（2015），pp.46比60[5] Bang-Jensen，J. 和M. M. Halldórsson，顶点着色边加权有向图，Inf.过程Lett. 115（2015），pp. 791-796。[6] Bermond，J.- C.的方法，F. Havet，F. Huc和C. L. Sale，加权网格和六边形图的不当着色，离散数学，算法和应用2（2010），pp. 395-411[7] Bodlaender，H. L.，A linear time algorithm for finding tree-decompositions of small treewidth，in： Proceedings of the twenty-fifth annual ACM symposium on Theory of computing，ACM ，1993，pp. 226-234.[8] Chlebiková，J.，Partial k-trees with maximum chromatic number，离散数学259（2002），pp. 269-276。[9] 考恩湖，W. Goddard和C.E. Jesurum，Defective Coloring Revisited，Journal of Graph Theory24（1997），pp. 205-219[10] 考恩湖J.，R. H. Cowen和D. R. Woodall，Defective colorings of graphs in surfaces：Partitions intosubgraphs of bounded valency，Journal of Graph Theory10（1986），pp.187-195.[11] 弗里克，M.，A survey of（m，k）-colorings，Annals of Discrete Mathematics55（1993），pp.45比57[12] 弗里克，M。和M. A. Henning，关于图的亏色的极值结果，离散数学126（1994），pp. 151比158[13] Gudmundsson ， B. 一 、 T. K. Magnusson 和 B.O. Saemundsson ， Bounds and fixed-parameteralgorithms for weighted inadequate coloring（扩展版）（2015）。[14] Harary，F.和K.Jones，条件可着色性ii：二分变化，Congressus Numerantium50（1985），pp. 205-218[15] Hayes，B.，Computing Science：The easyest hard problem，American Scientist（2002）. 113-117.[16] Hoefer，M.，T. Kesselheim和B.Vöcking，二次频谱拍卖的近似算法，ACM互联网技术交易（TOIT）14（2014），p.十六岁[17] 康河，巴西-地J.和C. McDiarmid，随机图的t-不当色数，组合数学，概率与计算19（2010），pp.87比98[18] 康河，巴西-地J.，T. Müller和J. - S. Sereni，（随机）单位圆盘图的不适当着色，离散数学308（2008），pp。 1438 - 1 4 5 4 年 ， 第 三 届 欧 洲 组 合 数 学 会 议 ， 图 论 与 应 用 。[19] K o lman ， P. ， B.Lidi ck y`andJ. - S.Sereni ， Fairedgedeletionproblemsont ree-ded eco so sablegraphsandinappropriate colorings ， Mandarin pt. 可 查 阅 http ： //orion 。数 学 现 在 。edu/lidicky/pub/kls10. pdf（2010年）。[20] 洛瓦什湖关于图的分解，Studia Scientiarum Mathematicarum Hungarica1（1966），pp. 237-238.[21] Rao ， M. ， 有 界 树 宽 和 树 宽 图 上 的 MSOL 分 割 问 题 ， Theoretical Computer Science377（2007），pp. 260-267[22] Tamura，H.，M. Sengoku，S. Shinoda和T. Abe，蜂窝移动系统中的信道分配问题和网络的新着色问题，IEICE电子、通信和计算机科学基础汇刊74（1991），pp.2983-2989年。