可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）523-533www.elsevier.com/locate/entcs正则图的全控制Carlos Hoppen1 Giovane Mansan2InstitutodeMatema'ticaeEst'ısticaUniversidadeFederal do Rio Grande do Sul PortoAlegre，Brazil摘要我们发现新的上界的大小的最小完全控制集的随机正则图和正则图与大围长。 这些界是通过分析一个局部算法得到的使用Hoppen和Wormald的方法[17]。关键词：全控制，随机正则图，大围长。1引言和主要结果本文研究图的全控制集。图G=（V，E）通常由一个顶点集V和一个边集E∈{{u，v}：u，v∈V，u=/v}组成.尽管我们使用标准的图论符号和术语，我们定义了出现在本文主要结果陈述中的概念。至于其他定义，我们请读者参阅[1]。有许多参数与图中控制的一般概念有关。研究最多的版本是图G=（V，E）的控制数γ（G）。一个集合S∈V是G的一个控制集，如果V\S中的每个顶点都与S中的某个顶点相邻。控制数是G的控制集的最小尺寸，即，γ（G）= min {|S|：S是G的支配集}。Cockayne、Dawes和Hedet-niemi[7]提出了以下相关概念。一个完全控制集S∈V是一个集合，使得每个顶点v∈V都是1电子邮件：choppen@ufrgs.com.br2电子邮件：giovanemansan@gmail.com3C. Hoppen 感 谢 CNPq （ 项 目 ） 的 支 持 。 308054/2018-0 ） ， 国 家 发展委员会。 G.曼 桑 感 谢 CoordenapércérsaodeA perfe ipércoame ntodePessoaldeN′pérsv elSuperior（CAPES）的支持。https://doi.org/10.1016/j.entcs.2019.08.0461571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。524C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523δ.Σ不2G与S中的顶点相邻。显然，任何完全控制集也是一个控制集，并且在一个图中存在完全控制集当且仅当它没有孤立的顶点。自然地，没有孤立点的图G的总控制数γt（G）γ t（G）= min {|S|：S是G的完全控制集}。计算γ（G）的值是一个众所周知的难题，它出现在Karp[19]提供的NP完全问题的原始列表中。Pfa Kazar，Laskar和Hedetniemi[20]证明了计算γt（G）也是NP-完全的。关于控制和完全控制的结果和参考文献，我们分别参考Haynes，Hedetniemi和Slater[13]和Henning和Yeo [15]。关于n阶图G的最小全控制集的大小，已有大量的上界和下界。由于一个顶点加到一个集合上只能支配它的邻居，所以很明显γt（G）≥n/Δ（G），其中Δ（G）表示G的最大度。另一方面，Henning和Yeo[15，定理5.1]证明了γt（G）≤1+ln（δ）n，其中δ（G）≥1是G的最小度. 一个自然的设置，用于比较这种类型是d-正则图，即每个顶点都与d条边，所以δ（G）= Δ（G）=d（我们总是假定nd是偶数）。在一般情况下，n-顶点d-正则图的最小全控制集的大小仍然可以有很大的变化.例如，如果G是一个不相交的完全二部图Kd，d的集合，我们有γt（G）=n/d，因为每个分支完全由二部图的每一边的一个顶点控制。这表明，对于所有d，上述γt（G）的平凡下界是尖锐的。另一方面，如果G是不交完全图的集合Kd+1，则γt（G）= 2n/（d+1），这是相当大的.表1给出了d-正则图G的最小全控制集的大小的上界Γ0（G）（实际上，这些上界是在δ（G）=d时得到的）. 事实证明，对于d∈ {2， 3， 4}的d-正则图，表中的上界是尖锐的。研究d -正则图上图论参数的行为的两种传统方法是考虑它的典型值，即它对随机选择的d-正则图的值，以及考虑它对具有大围长的图的值。图的围长是图中最短圈的长度。随机正则图的性质已经得到了深入的研究（参见[24]对此类概率模型结果的调查）。大围长对图的参数的影响也是一个有趣的问题，至少从ErdBesos[11]指出，对于任意给定的整数k和g，存在一个围长至少为g且色数至少为k的图，这表明了图的色数的整体性质.关于d-正则图G的大围长对全控制数的影响，Henning和Yeo [16]证明了：如果G是n-顶点图，δ（G）≥2，围长g≥3，则γ（G）≤. 1+1n。C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523525不不不不不不D不不不DΓ 0（G）/|V（G）|源ΓgD2三分之二见脚注41/ 2[16]3二分之一（2004年）0.488343/70。4285（2007年）0.41365十七/四十四0。3863[8]（2015年）0.365660。4653[15，定理5.1]0.3256表1本文给出了d -正则图G的最小全控制集的大小的上界，给出了参数γg（d，∞）的 上 界 Γ g 的相应的参考文献和近似结果。特别地，这表明当g→ ∞时，平凡下界对于2-正则图是渐近最优的。(This这个事实也可以通过观察长循环的完全控制集我们研究这个参数一般d。确切地说，对于d≥2和g0≥3，令γg（d，g0）：=sup{γt（G）/|V（G）|：G是d-正则的且围长g≥g0}，（1）即γg（d，g0）是围长至少为g0的d-正则图的最小可能上界. 这产生了一个单调序列随着g0的增加，我们考虑参数γ g（d，∞）= limγ g（d，g0）.（二）g0→∞Henning本文的一个主要结果（定理1.3），在下面将详细描述，它意味着对于某些固定的d值，γg（d，∞）的上界如下。定理1.1对于整数3≤d≤ 6，有γg（d，∞）≤Γg，其中 Γg的值为在表1中给出。td d我们现在考虑一个大的d-正则图的全控制数的典型值.为此，设Gn，d是n-顶点d-正则图的集合，对整数d≥2和常数ε>0，考虑γ R（d，ε）= infsup. γ（G）：G ∈ A.（三）A ∈Gn，d，n∈N，n|一|≥（1−ε）|Gn，d|注意，对于固定的d，γR（d，ε）是有界的，并且随着ε的减小而增加，因此，界限是明确的：γ R（d）= lim γ R（d，ε）。（四）t tε→0+526C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523D不D设Gn，d表示概率空间，样本空间Gn，d和均匀概率分布。能力分布在概率的语言中，找到上界rγ R（d）表示随机d-正则图渐近几乎必然（a.a.s.）有一个最小的全控制集，其大小至多为r。C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523527不不DD不不一个著名的构造，它使用随机d-正则图A.A.S.有一个小数目的有界长度的循环[5，25]，允许我们证明，γR（d）≤γg（d，∞），（5）因此，具有大围长的d-正则图的全控制数的任何确定性上界给出了全控制数的一个上界。 一个典型的d-正则图。这导致以下情况。定理1.2对于整数3 ≤d≤ 6，图G∈ Gn，d渐近几乎必然满足γ t（G）/n≤ Γ g，其中Γg的值如表1所示.事实上，在完全控制的背景下，（5）中给出的具有大围长的图和随机正则图的图参数的行为之间的联系实际上对许多不同的参数都成立，并且（5）是否等式成立是一个重要的开放性问题（参见Backhausz和Szegedy[3]对这一研究领域问题的详细描述最近，Wormald和第一作者[17]证明了上界γR（d）意味着γg（d，∞）的上界，只要它是通过分析一个本地算法，如他们的论文中所述。 （再次，前这句话将适用于除完全支配之外的一系列参数。）在本文中，这一结果由Hoppen和Wormald起着根本性的作用，作为工具，使我们能够转移的结果中获得的随机图的上下文中（定理1.2）的大围长的上下文中（定理1.1）。我们还应该提到，局部算法近似具有大围长的图的图参数的取值引起了人们的广泛关注。最近，Gamarnik和Sudan [12]表明，对于非常大的d，局部算法不能近似于最大独立集的大小，具有任意小乘法误差的大围长的d-正则图。Rahman和Vir'ag[21]改进了近似差距。我们的结果的证明使用[17]中描述的方法。我们使用Wormald[26]的方法，称为微分方程方法，来分析产生完全支配集的特定局部算法的性能当该算法应用于随机正则图时，在输入图G中G∈ Gn，d.然后我们利用[17，定理8.1]将这个结果推广到所有围长极大的图。微分方程方法是一种集中型的结果，已被证明是非常成功的随机过程的分析。 在随机正则图的特殊情况下，它已经被用来研究与控制有关的参数，见[9，10]，并且使用上述一般方法的大围长图的结果也在[18]中得到了证明。更精确地说，定理1.1和1.2是由下面的技术结果得出的，它对任何固定的d≥3都成立。定理1.3对任意d≥3和ε> 0，随机图G∈ Gn ， d渐近几乎必然包含一个全控制集DT<$V（G），使得|≤ n（q（x ∈）+ ε），|≤ n (q (x∗)+ ε),528C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523D其中z0（x）和q（x）是初始值问题（7）的解，并且x≠= inf{x>0：z0（x）= 0}。当我们分析第2节中描述的算法时，定理陈述中提到的微分方程组自然出现。用解析法计算q（x<$）的值并不容易，表1中的Γg值是这个量在某些d值下的数值近似值（小数点后第四位已经四舍五入）。这直接导致定理1.2的结论。为了推导定理1.1，我们只应用[17，定理8.1]，这要求我们检查算法满足[17]中描述的一组特定规则。本文其余部分的结构如下。在第2节中，我们提出了我们的算法，我们描述了进行分析的设置。第3节包含有关我们的主要结果的证明信息2产生小全控制集的一个启发式算法除了许多其他的应用，微分方程方法已被用来分析随机正则图上的大量算法的典型性能。在大多数应用中，这种方法的随机正则图，而不是直接工作与正则图，我们使用的一个proa choofBollob'as[5]，被称为配置模型，它考虑了以下概率空间，其元素可以通过以下简单的随机过程生成。从标记为1，...，n，每个桶中有d个点，并随机均匀选择（u.a.r.）配对P=a1，...，dn/2的点，使得每个ai是无序的点对，并且每个点恰好是一对ai。通常Pn，d表示配对的概率空间。通过将每个桶折叠成单个顶点，我们看到每个对对应于顶点集为1，...，n，每对都有一条边。一个在桶i和j中具有点的对产生连接顶点i和j的边。一个简单的计算表明，任何两个简单的d-正则图（即没有循环或多个边）的n个顶点是产生相同的概率。对于固定d，一个关键的性质是随机配对产生d-正则图的概率趋于正常数e（1-d2）/4，因为n趋于无穷（Bender和Canfield[4]），因此结果成立A.A.S.对于Pn中的随机配对，d也必须保持a.a.s.随机d-正则图我们按顺序选择对：可以使用任何规则选择对中的第一个点，只要第二个点是u.a.r.。从其余的点。我们称之为暴露对，这个属性是模型的独立属性为了简单起见，我们将参考图和顶点，即使我们指的是配对和桶。在这里，我们认为下面的启发式。我们从一个n-顶点图G0开始，其中没有边被暴露，并且具有一个集合D0=n。 其思想是通过顺序暴露图的边来生成一个随机d-正则图，同时生成一个完全控制集D。我们的构造过程是通过离散参数t标记的轮进行的。为C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523529≤j ≤d−每个t∈ {0，...，T C}，其中T C满足终止条件，我们产生G t+1和Dt+1分别从Gt和Dt(1) 选择顶点vtu.a.r.在Gt中的所有度为0的顶点中，暴露一个顶点ut与vt相邻。(2) 如果ut在Gt中的度为0，则暴露两个ut的所有剩余邻居和vt产生Gt+1并定义Dt+1=Dt<${vt，ut}。(3) 如果ut在G t中的次数不为0，则暴露ut的所有剩余邻居以产生G t+1，并定义D t+1=D t{ut}。注意，如果Gt生成一个简单图，则G t中度为0的顶点的集合Gt就是Dt中不受支配的顶点的集合.因此，这一系列的步骤应该执行，直到Gt不包含任何孤立的顶点。然而，由于与分析相关的技术原因，我们需要考虑额外的参数ε >0，并且我们执行该算法，直到Gt中0度的顶点数低于εn。然后在启发式结束时获得的集合DTC还不是完全控制集，但是可以通过添加尚未被控制的每个顶点的邻居而变成完全控制集。与该启发式关联的相关变量是Q（t）=|D t|和Y i（t），G t中度为i的顶点的个数，对于i∈ {0，...，d}。事实上，由于度为d的顶点不影响算法的其余应用，因此我们忽略变量Yd（t）。 我们写h t=（G0，.，G t）表示过程的历史到时间t（即，在实际应用启发式算法时获得的结果圆t）。 微分方程法的基本思想是跟踪每个变量在每一轮的期望值。如果满足某些技术条件，Wormald的强有力的结果，例如见[26，定理5.1]，意味着变量的实际值是a.a.s.。接近其预期价值，所有t∈ {0，.，T C}。 为了实现这些目标，我们将证明满足以下条件（我们观察到其中一些条件比实际需要的条件更强对于[26，定理5.1]）：(i) 存在一个绝对常数β=β（d），使得1≤Q（t+1）−Q（t）≤2且0max1|Yj（t+1）−Yj（t）| ≤β对于所有j∈ {0，...，d− 1}且所有t∈ {0，...， T D}。(ii) 存在函数f0，f1，. f d−1，f d：Rd+1→R且λ1=λ1（n）=o（1）使得对所有0 ≤ j ≤ d − 1，|h t ] − f j（t/n，Y 0（t）/ n，.|ht]−fj(t/n,Y0(t)/n, . . . ，Yd−1（t）/n）| ≤λ1（n）和|ht ] − f d（t/n，Y 0（t）/n，.，|h t] − f d (t/n, Y0 (t)/n,..., Y d−1（t）/n）|≤ λ1（n）对于所有t TD。530C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523..ΣΣ−-|ΣΣ.−λβ3+OS（t）卢恩(iii) 在（ii）中定义的函数fj在定义域中是Lipschitz连续的D{（t，z0，.，z d−1）：t≥ 0}，其中D是包含点=（x0，z0，.， z d−1）=（0，1，0，.，0），表示在算法开始时，Y i（0）= z i n，其中1 ≤ i ≤ d − 1。粗略地说，条件（i）告诉我们，变量不能在单轮启发式中发生实质性变化，条件（ii）告诉我们，变量的预期变化（以过程的历史为条件）可以计算出来，而条件（iii）告诉我们，这些预期变化由行为良好的函数描述。如果满足这些条件，则定理5.1 [26]建立了与函数fj相关联的微分方程系统具有唯一解（z0（x），...，z d−1（x），q（x）），初始条件z0（0）= 1，z i（0）=0，i≥ 1且q（0）= 0。此外，变量Q（t）和Yi（t）在整个过程中通过涉及（ii）中定义的函数的微分方程组的解来近似更准确地说，对于λ > λ1，存在一个绝对常数C，使得在概率为1−Oβ exp−nλ3的情况下，我们有Yj（t）/n=zj（t/n）+O（λ），Q（t）/n=q（t/n）+O（λ）（6）对所有的j和所有的0≤t≤σn，其中σ=σ（n）是所有x的上确界，使得微分方程组的解可以延伸到距离D的边界至多Cλ.3证明我们的主要结果在本节中，我们论证了前一节中描述的条件（i）、（ii）和（iii）对于我们的启发式是满足的。特别地，我们计算函数f0，...，f d−1，f d，它们产生了在定理1.3的陈述中提到的微分方程组。我们首先注意到β = 2d是（i）的平凡界，因为我们至多暴露2d1在每一轮的配对，涉及最多2D顶点。为了验证（ii），我们首先对每个变量X计算E[X（t+ 1）X（t）ht]。事实上，我们的过程中的条件期望可以基于Gt而不是在完整的历史ht中计算。我们可以证明E[Yj（t+1）−Yj（t）|Gt]d−1（d−i）Yi（t）i=1S（t）−δi，j+δ1，j+（d−i−1）（d−j+1）Yj−1（t）S（t）（d−j）Yj（t）S（t）−δ+dY0（t）−δ+（2d−2）。 （d−j+1）Yj−1（t）−（d−j）Yj（t）+O. 1Σ0，j并且S（t）0，jS（t）dY0（t）S（t）n. 1ΣΣΣE [Q（t +1）− Q（t）|Gt]= 1 +、=C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523531m=0Σ⎪⎩ΣΣ.−m=0zJ（x）=fj（x，z0，z1， . . . ，zd−1）对于所有0≤j≤d− 10，js（x）s（x）s（x）nγ+expλ-β3其中S（t）= d−1（d − m）Y m（t）和δ i，j是在{0，1}中取值的函数，使得δi，j= 1当且仅当i = j。度为j的顶点数的变化基本上取决于上一步中度为j和j-1的顶点数。将递归关系中涉及的量归一化，x：=t/n，yi（x）：=yi（xn）/n，q（x）：=Q（xn）/n，并且令n→ ∞，我们可以将递归关系看作以下微分方程组和初始条件的离散化：qJ（x）= f d（x，z0，z1，.， z d−1）z0（0）=1，zj（0）=0，1≤j≤d− 1，q（0）=0，其中函数fj定义为fj（x，z0，z1， . ，zd−1）（七）d−1（d−i）zi（x）i=1s（x）−δi，j+δ1，j+（d−i−1）（d−j+1）zj−1（x）s（x）（d−j）zj（x）s（x）−δ+dz0（x）−δ+（2d−2）。（d−j+1）zj−1（x）−（d−j）zj（x）对于j∈{0， . . . ， d−1}和s（x）=<$d−1（d−m）zm（x）。更重要的是，dz0（x）f（x，z，z，...，z）= 1 +.d01d−1s（x）在这一点上，我们已经找到了验证（ii）的函数f j，其中λ1= O（1/n）。接下来，我们需要定义一个域D∈Rd+1，满足（iii）。 对于ε > 0，设D ε包含所有元组（x，z0，z1，.，z d−1）∈Rd+1使得−ε< x<1，ε< z0<1+ ε和−ε/d 0，每个函数f j在D ε中是Lipschitz连续的。证明的草图。注意，每个fj是形式为p/s2的有理函数，其中p和s是d+1个变量的多元多项式，使得s不包含Dε中的根。Q如前一节所述，使用β= 2d，我们可以发现A >0足够大，使得λ（n）=A/n1/4至少有概率满足（6.β。nλ3.2个d.1/4磅8d3ΣΣ0，j1−O=532C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523n1/4exp−当n → ∞时，该表达式收敛于1。特别地，我们得出结论，Q（t）/n=q（t/n）+O（λ））在步骤σn之前以高概率保持。= 1−O.C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523533···−···−d−1s（x）−（2d−2）+s（x）s（x）（d−i−1我们仍然需要证明步骤σn发生在z0很小的区域中，这意味着我们可以对过程进行分析，直到输入图的几乎所有顶点都被完全支配。为了证明这一点，我们将建立微分方程组的解的性质下面的结果确保解zj（x）和q（x）位于区间[0， 1]内，对于所有x≥0的值，使得z0（x）>0。这意味着解的向量接近Dε的闭包的边界的原因是z0（x）接近0。命题3.2存在δ> 0使得对所有x ∈（0，δ]且0 ≤ j ≤ d − 1，我们有z j（x）> 0。证明的草图 这对于z0（x）来说是平凡的，因为它是连续的并且z0（0）=1。为了证明这个陈述对j≥1是正确的，它证明了zj（x）的一阶非零导数在x=0时是正的，这很容易通过对j的归纳来完成。Q下一个命题给出了zj（x）和s（x）的上界，前提是满足某些条件。命题3.3若zj（x）≥0且z0（x）>ε0，对所有x∈[0，θ]且所有j∈{1，.，d− 1}，其中ε0> 0且θ> 0，则s（x）≤ d且z j（x）≤ 1[0，θ]且所有j ∈ {0，...，d− 1}。证明的草图。设Z（x）= z0（x）+z1（x）+ + zd1（x）.观察Z J（x）=z0J（x） +z1J（x） ++zdJ1（x），其中，使用（7）中的微分方程，导致dz0（x）<$（d−（d−1））zd−1（x）<$$>dz0（x）<$（d−i）zi（x）<$s（x）i=1对于x∈[0，θ].注意，最后一个不等式是由s（x）≥dz0（x）≥dε0这一事实得出的。 这证明Z（x）在[0，θ]中是递减的。 由dZ（0）=dz0（0）=d=s（0）和dZ（x）≥s（x）得到s（x）≤d的结论为了限制z j（x），观察到，对于所有j ∈ {0，1，.，d− 1}，我们有1 ≥ Z（x）≥zj（x）和Z（0）= 1≥zj（0）。Q我们知道有θ> 0满足命题3.3的假设，即命题3.2的θ = δ。然而，当我们提到δ和θ时，我们总是指命题3.2和3.3的假设成立的δ和θ下一个结果，其初等（但稍微技术性）的证明被省略，意味着在所有函数zj（x）都为正的点之后，对于i≤d−2，函数zi+1（x）不能接近0，除非zi（x）接近0。命题3.4假设对所有x ∈ [δ，θ]和j ∈ {0，1，.，d− 1}。此外，假设存在i∈ {0，1，...，d−2}且ε i>0使得ε i≤min{zj（δ）/2 ： 0 ≤j≤d−1}且zi（x）>ε i。 则re是ε i+1>0，使得在[ δ，θ ]中zi +1（x）> ε i+1。设ε0>0是一个小于min{zj（δ）/2：0 ≤j≤d−1}的任意实数。对于合适的θ值，我们可以重复应用命题3.4，以获得{ε0，ε1，...，ε d−1}使得对于所有j∈{0，1，.，d− 1}。Z′（x）=−1−≤-1，534C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523定义θ0：= inf {x > δ：z j（x）= ε j，对于某些j}。这是很好的定义，因为对于所有j，zj（δ）>ε j，并且对于所有j，hz j（x）≥ 0的nyi nt val[δ，θ]，z 0 j（x）≤ − 1。 我们主张z0（θ0）=ε0. 实际上，假设zj（θ0）=εj，其中somj≥0。 命题3.4和z j的常数y确保zj−1（θ0）=ε j−1。我们得到z0（θ0）= ε0。图1.一、 z0（x）是r e d，z1（x）是blue e，z2（x）是green，q（x）是bla ck。 注意，图中没有描绘不在算法产生的完全支配集中的度为3的顶点。由此得出以下结论。命题3.5如果ε0>0小于min{zj（δj）/2 ： 0 ≤j≤d−1}，则存在θ0>δ使得z0（θ0）=ε0，并且对于所有x ∈ [δ，θ0]和j ∈ {0，1，.，d− 1}，z j（x）> 0。将命题3.2、3.3和3.5放在一起，由于z0（x）是递减的，并且在z0接近ε0之前没有其他变量可以接近Dε0的边界，我们得出以下结果。命题3.6对于d ≥ 3，考虑（7）中给出的初值问题。 固定ε > 0，令θ ε：= inf{x > 0：z0（x）= ε}。 然后，对于所有x∈ [0，θ ε]，我们有ε≤z0（x）≤ 1，0 ≤q（x）≤ 1和0 ≤z j（x）≤ 1，其中1 ≤j≤d− 1。证据它需要检查0 ≤q（x）≤ 1，因为其他陈述是前面命题的推论。为了说明为什么这成立，设l（x）= −z0（x）+ 1，则q（0）=l（0）= 0。此外，对于x∈ [0，θ ε]，我们有1 ≤ 1+ dz0（x）/s（x）=qJ（x）≤−z0J（x）=lJ（x）。因此，w e v e 0 ≤q（x）≤l（x）≤1 −ε。Q命题3.6告诉我们，当ε→0+时，z0趋向于0，因为对所有ε >0，它的导数对所有x∈[0，θε]小于−1。因此，常数x= inf {x> 0：z0（x）= 0}定义良好，我们证明了定理1.3。为了说明（7）的解的行为，我们在图1中显示了d = 3的解的计算近似。引用[1] 阿隆，N.，和J·斯宾塞概率方法。离散数学与最优化中的威利级数Wiley，2011.[2] Archdeacon，D.，J. Ellis-Monaghan，D. Fischer，D.弗朗切克，P.C.B.拉姆，S。西格湾韦河，巴西-地Yuster：关于统治的一些评论J. Graph Theory46（2004），207C. Hoppen，G.Mansan/电子笔记在理论计算机科学346（2019）523535[3] Backhausz ， A. ， 和 B.Szegedy ， 关 于 树 上 的 大 围 长 正 则 图 和 随 机 过 程 随 机 结 构 算 法 53 （ 3 ）（2018），389[4] Bender ， E. 一 、 和 E. R. Can Field ， 具 有 给 定 行 和 列 和 的 非 负 整 数 矩 阵 的 渐 近 数 ， Journal ofCombinatorial Theory，Series A，24（1978），296[5] 博洛布阿斯，B.，关 于n个标号正则图的一个渐近公式的概率推广，预印本系列，数学研究所，奥胡斯大学，1979。[6] 博洛布阿斯，B.， RandomG raphs. 学术出版社，伦敦，1985年。[7] Cockayne，E. J.，R. Dawes和S. T.海德涅米图的完全控制。Networks10（3）（1980），211-219.[8] Dor Wenling，M.，和M. A.亨宁5-一致超图中的横截与最小度为5的Mathematicae，38（2）（2015），155[9] 达克沃思，W.，和B. Mans，Randomized greedy algorithms for finding small k-dominant sets of randomregular graphs.Random Structures and Algorithms，27（3）（2005），401[10] 达克沃思，W.，和北卡罗来纳Wormald，关于随机正则图的独立控制数。Combinatorics，Probability andComputing，15（2006），513[11] ErdBesos，P.， 图论与概率。 加拿大数学杂志11（1959），34-38。[12] Gamarnik，D.和M.苏丹共和国.稀疏随机图上局部算法的极限。在第五届理论计算机科学创新会议论文集，ITCS'14，第369-376页，纽约，纽约，美国，2014年。ACM。[13] Haynes，T.，Hedetniemi，S.T.，和Slater，P.，图的控制基础。CRC Press，1998.[14] Henning，M.一、具有大全控制数的图。Journal of Graph Theory35（1），21-45（2000）.[15] Henning，M.一、和A.杨图的完全控制。Springer，2013.[16] Henning，M.一、和A.杨给定围长的图的全控制。图表组合24（2008），333-348.[17] Hoppen，C.，和N. C.蠕虫局部算法，大围长正则图，随机正则图。Combinatorica38（3）（2018），619[18] Hoppen，C.，和N. Wormald，通过局部算法求解具有大围长的正则图的性质。Journal of CombinatorialTheory，Series B121（2016），367[19] 卡普河M.，组合问题中的约简。计算机计算的复杂性，第85-103页。斯普林格，1972年。[20] Pfa J.，R. C. Laskar和S.T.海德涅米二部图的全连通控制与不可约控制的NP-完全性。技术报告428，部门Clemson大学数学科学（1983年）。[21] Rahman，M.， 和B. Vir'ag，Lo calalgorithmsforindepntsetsarehalf-optimal，AnnalsofProbability45（3）（2017），1543[22] 孙湖，加-地全控制数的一个上界J. 北京研究所Tech. 4（1995），111[23] 托马斯是的， 和A. 图的全控制与超图的小变换。Combinatorica27（2007），473[24] Wormald，N. C.的方法，随机正则图模型。伦敦数学学会讲义系列，第239-298页[25] Wormald，N. C.的方法，随机正则图中短圈的渐近分布，组合理论杂志，B辑，31168[26] Wormald，N. C.的方法，随机图过程的微分方程方法和贪心算法。近似和随机算法讲座，第73-155页，1999年
我的内容管理
展开
