没有合适的资源?快使用搜索试试~ 我知道了~
−−可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)229-240www.elsevier.com/locate/entcs将有向网格定理应用于FPT算法1、2Victor Campos,Raul Lopes,Ana Karolinna MaiaParGO集团,巴西联邦萨乌法国蒙彼利埃大学法国蒙彼利埃摘要网格定理最初由Robertson和Seymour于1986年证明,是结构图论领域最重要的工具之一,在无向图的算法设计中有许多应用。有向图中网格定理的一个类似版本由Johnson等人在2001年提出,最近由Kawarabayashi和Kreutzer在2015年证明。也就是说,他们证明了存在一个函数f(k),使得每一个有向树宽度至少为f(k)的有向图都包含一个大小为k的圆柱形网格作为黄油子图。此外,他们声称他们的证明可以转化为一个XP算法,参数为k,要么构造一个适当宽度的分解,要么找到声称的大圆柱形网格作为一个黄油子。本文对Kawarabayashi和Kreutzer的证明步骤进行了改进,将XP算法改进为FPT算法。证明的第一步是Johnson等人在2001年提出的XP算法,该算法决定了一个有向图D的有向树宽至多为3k2或允许k阶避风港. 值得一提的是,这个问题的FPT算法的skecth出现在2018年出版的《有向图的类》一书的第9章中,近似因子为5 k + 2。 我们的第一个贡献是将证明从约翰逊等人。找到一个树分解的宽度最多为3k2或k 阶 的 避 风 港在 FPT 时 间 内 , 通 过 使 用 重 要 的 分 隔 符 , 在 有 向 图 D 中 。然 后 , 我 们 遵 循 路 线 图 ,Kawarabayashi和Kreutzer通过局部改进某些步骤的复杂性来证明,特别是关于寻找大阶荆棘的碰集问题关键词:有向图,有向树宽,网格定理,FPT算法。1介绍宽度参数可以被看作是对给定图与典型结构的接近程度的估计。例如,图的树宽,特定的1 电 子邮件 :campos@lia.ufc.br ,raul. lia.ufc.brkarolmaia@lia.ufc.br , www.example.com ,ignasi.lirmm.fr2 工 作 得 到 项 目 CAPES/STIC-AmSud 88881.197438/2018-01 、 CNPq - Universal 项 目 425297/2016-0 、FUNCAP - PRONEM PNE-011200061.01.00/16 、 DEMOGRAPH ( ANR-16-CE 40 -0028 ) 和 ESIGMA(ANR-17-CE 23 -0010)的支持。https://doi.org/10.1016/j.entcs.2019.08.0211571-0661/© 2019由Elsevier B. V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。230诉Campos等人/理论计算机科学电子笔记346(2019)229对文献的兴趣,衡量图形可以通过以下方式近似的程度树。树宽有界的图的树分解因此,树分解揭示了图的一种形式的全局连通性度量:由于每个包中只能放置有限数量的顶点,因此许多小的 可以通过分解来识别图在有界树宽的图中,许多困难的问题可以通过利用经典的算法技术如动态编程或利用Courcelle定理[ 10 ]得到有效的解决基于树分解的算法的应用范围从频率分配问题到旅行推销员问题[9,20]。图的树宽首先在[2]中引入,然后在[16]中再次引入,最后在[26]中重新引入。关于这个问题的调查,我们请读者参阅[3]。鉴于基于无向图上宽度参数的应用取得了巨大的成功,毫不奇怪,人们有兴趣为有向图找到类似的定义。[17]在有向情况下对树宽的类似度量给出。有向图的有向树宽度度量其成为DAG的距离,并且有向图的树分解暴露了原始图的(强)连通性度量在[25]中可以找到无向和有向情况之间相似性的直觉。人们自然会问,对于树宽很大的图,我们可以说些什么。结构图论中最相关的结果之一是树宽较大的图包含较大的网格子式。 更准确地说,网格定理[26]指出存在一个函数f:N→N使得树宽至少为f(k)图包含一个k×k网格作为子网格。最近给出了一个多项式函数在[7]中。值得一提的是,有时,大的树宽(因此,存在大的网格子式)意味着我们实际上正在处理特定问题的正例。一个这样的情况是最长路径问题。在[12]中,给出了一个框架,可以为许多这样的问题生成固定参数算法,称为二维问 题 。 该 列 表 包 括 VERTEX COVER 、 FEEDBA cK VERTEX SET 、 MMINIMUMMAXIMAL MATCHING、DOMINATING SET、EDGE DOMINATING SET以及许多其他。这项开创性的工作被称为二维性。作为应用网格定理的另一个例子,考虑k维的ISJOINT路径问题.它通过以下方法在一般图上以多项式时间求解[27]。如果输入图具有有界树宽,则通过标准动态规划技术直接解决问题。如果不是,那么根据网格定理,该图包含一个大网格。 现在,我们可以证明,如果对该实例的解决方案使用了“非常深”到网格中的顶点,则该解决方案可以被重新路由以避开这样的顶点。直到图满足一组属性(在这种情况下,包括具有小树宽),诉Campos等人/理论计算机科学电子笔记346(2019)229231一个不相关的顶点,也就是说,一个顶点,当删除时不会改变问题的答案,可以被验证。这导致了一个迭代算法,将问题减少到一个更小的实例,直到它满足问题可处理的条件。这种不相关的顶点技术被广泛用于许多不同的问题(参见。[15,19],例如。对于有向情形,给出了由Johnson等人[17]和最近由Kawarabayashi和Kreutzer [18]证明。也就是说,在[18]中示出,存在函数f:N→N,使得有向树宽度至少为f(k)的每个有向图包含圆柱网格,命令k作为黄油小调3. 导言中提到的所有对象的定义都可以在第2节中找到。文[18]给出的有向网格定理的证明是构造性的。他们从[17]的结果开始,即在XP时间,给定有向图D和整数参数k,输出D的树实分解的宽度至多为3k− 2或k阶的避风港H。从这里,在[18]中,他们从H得到了[k/2]阶的荆棘B。对于B,它们给出子一个一致性结构,不能容易地适应XP算法,因为使用了荆棘的详尽描述,并且不能保证k阶的荆棘具有由k的函数限定的大小。从P和A开始,有向网格定理[18]的其余证明在FPT时间内运行,参数为k。本文的主要贡献是一个FPT算法,给定D和k,要么产生一个宽度最多为3k−2的径向分解,要么输出一个路径P包含一个大小恰好为k的良好链接集合A。 我们的算法这是他的想法[17,18]。在定理2.9中,我们给出了一个FPT算法,给定有向图D和参数k,输出树实分解D的宽度至多为3k− 2或k阶的避风港H。我们承认在[1,定理9.4.4]中提到了一个类似的结果,但是近似因子为5k+ 10,并且只包含了一个不完整的证明草图。在第4节中,我们展示了如何从H获得k阶荆棘B的紧致定义。这种紧凑的定义用于避免对可拆卸元件的计数。在引理4.9我们使用B找到一条路径P,该路径P包含一个k阶的良链集A,FPT时间。我们利用[14]中给出的FPT算法,该算法解决了有向图的多割问题的一个图1给出了上述算法的路线图。 我们用虚线弧标记[18]的步骤,这些步骤已经是FPT并且不需要进行调整。所有其他弧代表我们在本文中采用的步骤2正式定义和分类在这一节中,我们给出本文的相关定义,并提到一些已知的结果和关于下面定义的对象的关系。本节的内容主要基于[17]。[18 ]的完整版本可以在www.example.com上https://arxiv.org/abs/1411.5681。包含一个大小约为k/2。特别是,建筑232诉Campos等人/理论计算机科学电子笔记346(2019)229(D,k)还k阶好吧--第4节荆棘k阶引理4.9定理2.9链接集合与路径P[18树栖宽度分解≤3k− 2图1.一、在有向网格定理的证明中使用的算法的草图[18]。2.1参数复杂性关于参数化复杂性的基本背景,我们请读者参考[11,13],这里我们只回顾一些基本的定义。参数化问题是一种语言L×N. 对于一个实例I=(x,k)∈N,k称为参数。一个参数化问题是固定参数易处理的(FPT),如果存在一个算法A,一个可计算函数f,和一个常数c,使得给定一个实例I=(x,k),A(称为FPT算法)正确地决定I是否在时间上由f(k)限制。|我|C. 比如说,V ERTEXC OVER问题参数化是FPT。一个参数化问题是XP中的,如果存在算法A和两个可计算函数f和g,使得给定实例I=(x,k),A(称为XP算法)正确地判定I是否在时间上以f(k)为界∈ L。|我|g(k)。例如,由解决方案的大小参数化的C语言问题在XP中。在参数化问题中,类W[1]可以被看作是经典决策问题类NP的参数化等价。在不进入细节的情况下(参见[11,13]的正式定义),参数化问题是W[1]-hard可以被视为这个问题不是FPT的有力证据。W[1]-hard问题的典型例子是由解的大小参数化的C liquue2.2树木分解和障碍物关于图论的基本背景,我们请读者参考[4],这里只回顾一些基本的定义。除非另有说明,否则下文提及的所有路径均被视为定向的。 对于图G=(V,E),有向图和无向图,X<$V(G),我们将G中删除X后的图记为G\X。树形图R是指一棵以r为根的树的所有边都指向远离r的方向。如果R的一个顶点v的出度为零,我们说v是R的一个叶。 我们现在定义有向图的保护集和树实分解。从这里开始,除非另有说明,否则我们仅指定向边。D总是代表有向图,G代表无向图。定义2.1[Z-守护集]设Z是V(D)的子集,S∈V(D)\Z。诉Campos等人/理论计算机科学电子笔记346(2019)229233我们说S是Z-守卫的,如果D\Z中没有第一个和最后一个顶点在S中的有向行走使用D\(Z<$S)的顶点。如果一个集合S是Z-守卫的,我们也可以说Z是S的守卫. 我们注意到,在[17]中,作者使用了Z-正规集而不是Z-保护集.设R是树形图,r ∈ V(R),e ∈ E(R),RJ是e的头. 我们说r > e,如果r = rJ或r > rJ。我们还说,如果r是的头或尾,e.有向图的树宽定义如下。定义2.2[树分解和有向树宽]有向图D的树分解是一个三元组(R,X,W),其中R是一个树形图,X={Xe:e∈E(R)},W={Wr:r∈V(R)},X,W是D的顶点集的集合(称为袋),使得(D1)W是V(D)的非空集划分;(D2)若e∈E(R),则{Wr:r∈V(R),r > e}是Xe-守护的.对于顶点r∈V(R),我们将r的宽度称为|W r(erX e)|. 宽度的(R,X,W)是最小整数k,使得对所有r∈V(R),width(r)≤k+1。D的有向树宽,记为dtw(D),是最小整数k,使得D具有宽度为k的树型分解。定义2.3[Nice arboreal decomposition.]我们说有向图D的树分解(R,X,W)是好的,如果(i) 对任意e∈E(R),Wr诱导D\Xe的强分支;(ii) 若r ∈V(R)且r1,...,rl是r在R中的外邻居,则1≤i≤l我很抱歉。Xe=。埃布尔我们现在定义一些大的有向树宽度的阻塞结构。定义2.4[良链集]设D是有向图,A∈V(D)。我们说A是良链的,如果对所有X,Y∈A,|X|为|Y|=k,则D中从X到Y有k条顶点不交路。注意,我们总是可以假设X<$Y=A。我们总是可以在X和Y中包含A的所有顶点,这些顶点最初不在X或Y中,因为X<$Y中的每个顶点都是从X到Y的有向路径。定义2.5[有向图中的避风港]设D是有向图。 D中的k阶避风港是分配给每个集合Z<$V(D)的函数β,其中|Z| ≤k− 1,D \ Z的一个强分支的顶点集,如果ZJ<$Z<$V(D),则β(Z)<$β(ZJ)。D的避风港数是最大的k,使得D允许一个k阶避风港。234诉Campos等人/理论计算机科学电子笔记346(2019)229无向图的避风港数与树宽之间存在着直接的关系。无向图中的避风港定义类似。函数β保留了它的所有性质,但将至多k−1个顶点的集合映射到删除这些顶点后的图的分量定理2.6 [28]设G是一个图,k ≥ 0是一个整数. 则G有一个k阶的避风港当且仅当它的树宽至少为k− 1。对于有向图,只有一个前一个结果的含义是真的。定理2.7 [17]设D是有向图,k是非负整数。如果D有k阶的避风港,则dtw(D)≥ k − 1。对于定理2.7的相反方向,只知道一个近似的版本。定理2.8 [17]设D是有向图,k是正整数. 然后要么dtw(D)≤ 3 k − 2或D容许k阶避风港。在[17]中给出的定理2.8的证明产生了一个XP算法,该算法决定有向图D是否允许k阶的避风港或产生D的宽度至多为3k− 2的树实分解此外,虽然在文章中没有明确提到,但该算法实际上为D产生了一个很好的(如定义2.3所示)树型分解,并且可以用作一个过程,一个有向图DJ使得dtw(DJ)≤k−2,生成一个很好的树分解,DJ的宽度至多为3k− 2。 在第3节中,通过利用多个UT[5,8]问题的一个变体,我们提供了一个具有相同输出的FPT算法定理2.9(第一个主要贡献)设D是有向图,k是非负整数. 有一个FPT算法,参数为k,它决定D是否允许k阶的避风港或产生D的树分解,其宽度至多为3 k− 2。有向网格定理[18]的证明始于判定有向图是否具有有界有向树宽度。定理2.9是证明推论2.13的第一步。接下来,我们定义了一个结构,它将有助于在大有向树宽度的有向图定义2.10【有向图中的荆棘】A brambleB={B1,.,B1}是有向图D的强连通子图族,使得如果{B,BJ}<$B则B<$BJ/=<$或D中存在从B到BJ和从BJ到b荆棘B的一个碰集是一个集合C<$V(D),使得对所有B∈ B,C<$B/=<$。荆棘B的序order(B)是命中B的集合的最小大小。有向图D的荆棘数记为bn(D),是有向图D的最大荆棘k,使得D允许k阶荆棘。高阶荆棘也是有向网格定理原始证明的关键。在第4节中,我们展示了如何从一条与所有诉Campos等人/理论计算机科学电子笔记346(2019)229235问题P输入:参数:k和r。一个有向图D和一个集合T∈V(D),|不|≤ 2 k− 1。问:是否存在一个至多有r个顶点的集合Z∈V(D),使得每个D\Z满足的强分支C|V(C)| 3 k−2,正如推论2.13的第一步证明所要求的那样。我们使用下面的主张,也取自[17]。我们包括一个简短的完整性证明。3.2设D是图,T∈V(D),|不|≤ 2 k− 1。如果(D,T,k,k− 1)是P的负例,则D允许k阶避风港。我们建议读者参考[8,21,22,24],以获得无向和有向情况下多割和多路割的正式定义以及相关结果。我们只正式定义了称为线性割的有向多割的变化[14]。在线性边CUT问题中,我们给定一个图D,一个集合{T1,...,Tl}的子集,我们想要找到一个最小的边集Z,使得在DJ=(V,E-Z)中,当j >i时,没有从Ti到Tj的路径。这个问题是FPT时,参数的大小的解决方案。定理3.3[14]线性边CUT问题是FPT,当参数为解的大小r时,可以在O(4 r·r·n4)的时间内解决。顶点版本定义如下。线性VERTEXCUT输入:有向图D和终端集T的集合,其中T ={T1,T2,. T l},其中T i∈V(D),对于i∈ {1,.,l}。参数:r.问题:是否存在一组顶点Z<$V(D),|Z| ≤r,使得在D\Z中没有从Ti到T j的路,其中1 ≤ i< j ≤ l?在这一节中,我们将展示如何将线性V边CUT问题简化为线性边CUT问题。因此,根据定理3.3,我们得到了线性V-顶点问题的FPT推论3.4对于线性V-顶点C UT问题,存在一个FPT算法,其参数为解的大小r,时间复杂度为O(4 r·r·n4)。接下来,我们证明了P的一个实例的任何解也是线性VERTEX CUT问题的一个相关实例的解。引理3.5设(D,T,k,r)是p 的 一个 实例。 Z是一个解,(D,T,k,r)当且仅当存在T − Z的一个划分T为集合T1,T2,.,Tl诉Campos等人/理论计算机科学电子笔记346(2019)229237使得|我不是|≤ k − 1,对于i ∈ {1,..., l},Z是实 例 的解(D,T,r)的线性V-顶点C UT问题。问题p的FPT算法由引理3.5和推论3.4得出。运行时间严重依赖于可以从p的实例(D,T,k,r)的给定集合T生成的分区T的数量。这个值由k阶Bell数[6]限定。第k个有序贝尔数计数大小为k的集合的有序分区的数量,并且具有2O(klogk)的形式。引理3.6问题P是FPT中的问题,可以在时间2 O(klogk)·n O(1)内解决。我们现在准备陈述本节的主要结果。我们注意到,证明遵循[17,定理3.3],只是我们用FPT算法代替了证明的XP过程定理3.7设D是有向图,k是非负整数。 有一个FPT算法,参数为k,它要么得出D允许一个k阶的避风港,要么得出D的一个很好的树分解,其宽度至多为3 k − 2。此外,如果该算法得出结论,存在k阶的避风港,则它输出一个集合T V(D),其中|不|= 2 k −1使得(D,T,k,k − 1)是p的负实例。算法的时间复杂度为2 O(klogk)·n O(1).在下一节中,我们提供了第二步,也是最后一步,在[18]中包含的证明中需要修改。4找到一个链接良好的路径已知从有向图D中任意k+1阶的避风港,都可以在D中找到k/2阶的荆棘[23,引理6.4.20]。这个过程通过枚举所有大小不超过k/2的集合Z的所有集合β(Z)来生成荆棘集BJ,并且我们可以通过遍历给定集合X的所有元素来验证它是否是BJ在第3节中,我们提供了一个FPT算法,参数为k,该算法要么生成一个由k的函数限定的宽度的树分解,要么输出一个集合T大小至多为2k− 1,使得(D,T,k,k−1)是问题的负例P.在本节中,我们使用T来识别高阶的荆棘B,比BJ 在下面的意义上:只有B的紧凑描述,我们可以使用第3节中描述的方法来计算具有参数k的FPT时间中B的命中集。在下文中,我们定义了一种特殊类型的荆棘,可以用来实现这种紧凑的描述,并证明了它的命中集的一些性质定义4.1设D是有向图,T是V(D)的子集,使得|≤ 2 k − 1。| ≤ 2 k − 1.D的T-bramble是bramble B使得B ={B<$D|B是诱导的,强连接的,并且|V(B)|≥ k}。对于本节的剩余部分,除非另有说明,令(D,T,k,k−1)是P的负实例,BT是D的T-bramble。首先我们证明order(BT)=k。238诉Campos等人/理论计算机科学电子笔记346(2019)229B4.2 B T是D中k阶的荆棘。请注意,作为|不|≤ 2 k−1,B T的任何两个元素相交,且任何BJ<$BT是阶至多为k的荆棘。下一个引理也是展示本节主要结果所必需的。引理4.3 [18]设B是有向图D的荆棘。 在多项式时间内,我们总是可以在D中找到一条路径P,使得V(P)是B的一个碰集。我们想修改下一个引理,使它的陈述可以在FPT时间内被验证。这正是实现有向网格定理的FPT引理4.4 [18]设D是一个有向图,B是一个k(k +2)阶的荆棘,P =P(B)是与每个B ∈ B相交的一条路。 然后有一个大小为k的集合A V(P),它是良好链接的。要做到这一点,我们需要展示如何将B分裂成阶至少为[k/2]的更小的荆棘,这些荆棘被P(B)的子路径包围我们可以迭代地增长P的PJ的子路径,同时在每次迭代中检查相交V(PJ)的元素的集合是否是足够阶的荆棘这可以通过枚举给定荆棘的所有元素来完成,这不是我们针对FPT算法时可以进行的过程。为了更有效地做到这一点,我们利用了我们对荆棘BT的特殊选择所赋予的一些性质。定义4.5设X∈V(D),B是D的一个bramble。我们定义B(X)为B与X相交的元 素 。 类似地,我们定义B<$(X )为B与X 不 相 交 的 元素 。 Formall y,B(X)={B∈B|V(B)X=/B(X)={B∈B|V(B)<$X=<$}。注意,B(X)和B′(X)是可重构的,因为b0th是可 重构B的子集。另外,B(X)与B ′(X)是不相交的,B(X)的一个碰集与B ′(X)的一个碰集的并是B的一个碰集.从这句话,我们有,ord(B(X))+ord(B<$(X))≥ord(B)虽然B(X)的阶可能很难计算,但我们可以通过知道它的“补块”B <$(X)的阶来估计它的阶.考虑BT、BT(X)和BT(X)这三个条件。下面的结论表明,击中集f或B<$T(X)是p的实例(D\X,T−X,k,k)的精确解,并且通过引理3.6,可以在FPT时间内找到。4.6LetX,Z=V(D)。设B∈B<$T(X)使得V(B)<$Z=<$当且仅当D\(Z<$X)包含强连通分支C,使得|≥k。| ≥ k.权利要求4.6c的对比性特征在于B<$T(X)的碰集。4.7LetX,Z=V(D).Z是B<$T(X)的碰集当且仅当D\(X <$Z)的每个强分支至多包含T − X的k − 1个顶点。诉Campos等人/理论计算机科学电子笔记346(2019)229239因此,我们可以通过求解p的实例(D \ X,T − X,k,r)来决定ord(B<$T(X))≤r。下面的结果是引理3.6和权利要求4.7的直接结果。推论4.8对于任意X∈V(D),存在一个FPT算法,在时间2O(klogk)·nO(1),它决定了ord(B<$T(X))≤r或ord(B<$T(X))≥r+1.最后,我们遵循[18,引理4.4]的原始证明,但在FPT时间内选择P的子路径引理4.9设D是有向图,g(k)=(k+1)([k/2 <$+1])− 1,T<$V(D),其中|不|= 2 g(k)− 1,并假设(D,T,g(k),g(k)− 1)是p的负实例。 设BT是D的g(k)阶T-荆棘,P是与BT中每个元素相交的路.然后有一个k阶的集合AV(P)是良链的。此外,可以在FPT时间中找到A,参数为k。最后一个引理展示了如何在有向树宽度很大的有向图D 通过遵循有向网格定理[18]的剩余证明,它为所有剩余步骤产生FPT算法,我们可以验证推论2.13。引用[1] Bang-Jensen,J.和G. Gregory,[2] 贝尔泰勒湾和F. Brioschi,“非串行动态规划”,学术出版社,美国佛罗里达州奥兰多,1972年。[3] Bodlaender,H.L.,Treewide:characterizations,applications,and computations,in:Proc. 第32届计算机科学中的图论概念国际研讨会(WG),LNCS 4271,2006年,pp. 1-14号。[4] Bondy,A.和M.R. Murty,[5] Bousquet,N.,J. Daligault和S. Multicut是fpt,SIAM Journal on Computing47(2018),pp. 166-207.网址https://doi.org/10.1137/140961808[6] Cayley,A.,“在被称为树的分析形式上。第二部分,112115[7]切库里角和j.Chuzhoy,网格子式定理的多项式边界,ACM杂志63(2016),pp. 40:1-40:65。网址http://doi.acm.org/10.1145/2820609[8] 奇尼斯河M. Hajiaghayi和D.马克思,固定参数的有向多路切割参数化的割集的大小,在:Proc. 第23届ACM-SIAM离散算法研讨会(SODA),2012年,pp。1713-1725年。[9] 库克,W。和P. D。Seymour,Tour merging via branch-decompositions,INFORMS Journal onComputing15(2003),pp. 233-248。[10] Courcelle,B.,图的一元二阶逻辑。I.可识别的有限图集,信息和计算85(1990),pp。12比75URLhttp://www.sciencedirect.com/science/article/pii/089054019090043H[11] Cygan,M.,F. 弗明湖Kowalik,D.Lokshtanov,D.马克思,M。Pilipczuk,M.Pilipczuk和S. Saurabh,[12] Demaine,D.,V. Fomin,M. Hajiaghayi和D. M. Thilikos,Subexponential parameterized algorithms onbounded-genus graphs and H-minor-free graphs,Journal of the ACM52(2005),pp. 866-893240诉Campos等人/理论计算机科学电子笔记346(2019)229[13] 唐尼河G.和M. R. Fellows,[14] 埃尔巴赫尔河F.、T. Jaeger,N. Talele和J. Teutsch,具有线性有序终端的定向多路切割,CoRRabs/1407.7498(2014)。[15] Grohe , M. , K.- I. Kawarabayashi , D. Marx 和 P. Wollan , Finding topological subgraphs is fixed-parameter tractable,在:Proc. 第43届ACM计算理论研讨会(Stoc),2011年,pp. 479-488.[16] 哈林河图的S-函数,Journal of Geometry8(1976),pp.171-186。URLhttps://doi.org/10.1007/BF01917434[17] 约翰逊,T.,N.罗伯逊警察局Seymour和R. Thomas,Directed tree-width,Journal ofCombinatorial Theory,Series B82(2001),pp.138-154。[18] Kawarabayashi,K.- I.和S. Kreutzer,有向网格定理,在:第47届ACM计算理论研讨会(STOC),2015年,第47页。655-664。URLhttp://doi.acm.org/10.1145/2746539.2746586[19] Kleinberg,J.M.,不可分割的路径问题和半不相交路径问题的决策算法,在:Proc. of the 30th AnnualACM Symposium on Theory of Computing(STOC),1998,pp.530-539[20] Koster,A.,S. van Hocker和A.Kolen,通过树分解解决频率分配问题,离散数学电子笔记3(1999),pp.102比105[21] Kratsch,S.,M. Pilipczuk,M. Pilipczuk和M. Wahlstrm,Fixed-parameter tractability of multicut indirected acyclic graphs,SIAM Journal on Discrete Mathematics29(2015),pp.122-144网址https://doi.org/10.1137/120904202[22] Marx,D.和I. Razgon,由割集大小参数化的多割的固定参数可处理性,SIAM Journal on Computing43(2014),pp.355-388.网址https://doi.org/10.1137/110855247[23] Matthias,D.和F. Emmert-Streib,[24] Pili pczuk,M. 和M. Wahlstr?om,Directedmulticutisw[1]-ha rd,evenforfourterminalpairs,ACMTransactions on Computation Theory 10(2018),pp. 13:1-13:18。网址http://doi.acm.org/10.1145/3201775[25] Reed,B.,引入定向树宽,离散数学中的电子笔记3(1999),pp。222- 229[26] Robertson,N.和P. D。西摩,小图。V.排除平面图,组合理论杂志,系列B 41(1986),pp。92比114[27] Robertson,N.和P. D。西摩,小图。十三. The disjoint paths problem,Journal of CombinatorialTheory,Series B 63(1995). 65比110URLhttp://www.sciencedirect.com/science/article/pii/S0095895685710064[28] 西摩警局和R. Thomas,Graph searching and a min-max theorem for tree-width,Journal ofCombinatorial Theory,Series B58(1993),pp.22比33URLhttp://www.sciencedirect.com/science/article/pii/S0095895683710270
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功