【摘 要】
：
设G=（V,E）是一个图,其中V是有限的顶点集,边集E为V的某些二元子集构成的集族.超图H=（V,E）是图的推广,边集E为V的某些子集构成的集族.图的树宽定义为其树分解宽度的最小值.树宽是算法图论和结构图论中的重要参数.许多NP-完全问题在将树宽作为参数的条件下,是可以多项式时间求解的.然而判定任意图的树宽是否小于等于某个给定常数k被证明是NP-完全问题.因此确定特殊图类树宽的精确值或上下界就显得
论文部分内容阅读
设G=（V,E）是一个图,其中V是有限的顶点集,边集E为V的某些二元子集构成的集族.超图H=（V,E）是图的推广,边集E为V的某些子集构成的集族.图的树宽定义为其树分解宽度的最小值.树宽是算法图论和结构图论中的重要参数.许多NP-完全问题在将树宽作为参数的条件下,是可以多项式时间求解的.然而判定任意图的树宽是否小于等于某个给定常数k被证明是NP-完全问题.因此确定特殊图类树宽的精确值或上下界就显得尤为重要.本文的主要研究成果如下:1.对广义Kneser图K（n,k,t）,在n,k,t满足一定条件时,我们证明了其树宽的精确值;对t=k-1时,我们给出了全部的n,k关系下K（n,k,k-1）的精确值.并且根据著名的Erd（?）s-Ko-Rado定理给出了广义Kneser图树宽取到精确值的树分解.2.对线性超图H的二截口图类[H]2,我们分别给出了以H的平均秩,最小秩作为主项的树宽的下界.前者为差1紧的,后者为紧的.我们提出了超树宽的概念,并给出了[H]2的树宽关于H的超树宽的上界,此界也是紧的.3.我们提出了完全子图类问题的概念,并在树宽有界的条件下,给出了完全子图覆盖问题、完全子图染色问题和完全子图完美匹配计数问题的参数化算法.以完全子图覆盖问题为例,当取完全子图集分别为所有的团、边集和超边在其二截口中对应的完全子图时,我们可以对应地得到团覆盖问题,图的顶点覆盖问题和超图的顶点覆盖问题的参数化算法.4.在树宽有界的条件下,使用快速集合卷积,给出了w-控制集问题的参数化算法,并改进了完全子图完美匹配计数问题的复杂度.
其他文献
马尔科夫决策过程作为一类随机控制过程,自Bellman上世纪五十年代提出并系统研究以来,已取得丰富的理论成果和广泛的应用。最优策略的存在与求解、最优函数的确定等,是马尔科夫决策模型研究中的几个核心问题。本论文研究了一类特殊的马尔科夫决策模型,这类模型是通过状态增量的迭代来定义的。其增量由随机噪声决定,我们通过引进随机行动来控制噪声的影响。针对该模型特点,我们提出了一类新的研究思路,通过研究轨道的极
研究背景和目的:乳腺癌（Breast cancer,BC）是女性最常见的肿瘤,也是肿瘤死亡的主要原因。目前BC的治疗手段包括手术治疗、放疗、化疗、内分泌治疗以及靶向治疗,虽然上述方法能降低BC的死亡率,但考虑BC发病率的逐年上升,发病年龄逐渐年轻,寻找新的治疗方法和手段来降低BC的复发率,提高患者的生存率变得尤为重要。他汀类药物是一种3-羟基-3-甲基戊二酰辅酶A（HMG-CoA）还原酶抑制剂,其
“双碳”目标的发展背景下,页岩气产业具有很大的发展潜力。由于我国地理条件、页岩气开采的岩层深度等因素,在页岩气开采过程中需要添加钻井液,因此不可避免的会产生大量的废弃油基岩屑,油基岩屑的处理对页岩气产业的发展有很大的影响。随着人们生活品质的提高,国家对环保的要求也越来越高,因此对油基岩屑的处理也有更高的要求。传统的热解、生物、化学等处理手段存在着二次污染、处理周期长等许多问题,同时也未关注油基岩屑
地中海贫血是儿童最常见的一种遗传性血液系统疾病,根据基因型的不同可分为以下4种类型:α-地中海贫血、β-地中海贫血、δβ-地中海贫血、δ-地中海贫血以及其他少见的地中海贫血,其中α-及β-地中海贫血最常见。慢性溶血性贫血是地中海贫血主要的临床表现,根据临床表现的严重程度将β-地中海贫血分为轻型、中间型和重型。造血干细胞移植是目前β-重型地中海贫血唯一根治方案。人类白细胞抗原（HLA）在造血干细胞移
1、研究目的1.1 寻找副肾动脉预测因素,构建副肾动脉预测模型并验证其预测效能;1.2 寻找肿瘤肾段供血动脉预测因素,构建肿瘤多肾段动脉供血预测模型并验证其预测效能;1.3 探索三维重建模型对腹腔镜肾癌手术的指导作用。2、研究方法2.1 构建副肾动脉预测模型并验证其诊断效能收集2015年12月至2020年10月共170例cT1-cT3期肾癌患者的术前CT图像,利用UroMedix-3D软件重建肾脏
曝气设备充氧能力测试不仅是矿业和工业废水处理中单元操作环节，也是我国高效给排水科学与工程教学中一个非常重要的实验。本文通过三种方法（方法一、二、三）计算氧总传递速率，得出本次实验机械曝气的氧总传递速率分别为0.1633、0.1765和0.0075。根据1n（Cs-C）与t的拟合关系曲线，发现方法一的拟合程度更高，表明该方法获得的氧总传递速率更合理。本实验技术研究为计算曝气设备氧的总传递系数提供了重
研究目的:药物诱导的肝损伤是药物在临床前试验阶段被撤回的主要原因。因此,为了节省药物开发的成本,并且及时预估药物可能带来的药物肝毒性,开发一种具有良好的预测能力的体外模型具有非常重要的意义。现如今,体外培养的肝细胞已经被广泛用于药物不良反应的预测,其中,由于操作方法简单,成本低廉,二维状态培养下的肝细胞被广泛应用。然而许多研究表明,这种状态下的肝细胞因为形态上的改变、发生内皮-间充质转变等原因,导
来自Toda系统、二阶和四阶共形协变椭圆偏微分方程中有很多重要且具有挑战性的课题,它们在物理与几何等领域中有着深厚的背景和应用。这些方程和方程组吸引了很多学者的兴趣,数学家们对其做出了大量杰出工作。这些方程（组）的共同点之一是它们的解均表现一定的能量集中爆破现象,研究爆破解对于理解它们至关重要。本文旨在运用爆破分析和椭圆方程经典理论等理论方法来研究这些方程（组）爆破解的性质,并给出部分应用。首先,
研究背景和目的随着全球恶性肿瘤发病率的逐年递增,宫颈癌（Cervical Cancer）已在国内外女性生殖系统常见恶性肿瘤中高居第二位,并且其发病及死亡在全部女性恶性肿瘤中排名第四[1]。高危人乳头瘤病毒（HR-HPV）感染已被证实与宫颈癌、宫颈上皮内瘤变和口咽癌等疾病高度相关[2,3]。5-氨基酮戊酸介导的光动力疗法（ALA-PDT）作为一种极具前景的治疗手段,临床上已用于多种HR-HPV感染相