图切割问题的核心化及参数算法研究

论文摘要

图切割问题一直以来都是组合优化领域中经典并且活跃的主题,对此类问题的研究不仅对多物网络流问题、模糊聚类编辑问题（Fuzzy Cluster Editing）.有向图中的反馈顶点集问题（DFVS）等许多研究难题具有重大的理论意义,而且对并行和分布式计算、VLSI芯片设计、电路设计、计算机视觉、计算机通信网络可靠性和鲁棒性研究等众多的实际应用领域也具有十分重要的现实意义。许多著名的图切割问题,如多端割问题、多割问题、最大割问题、k-切割问题等,都是经典的NP难解问题。本文主要以边-多端割问题和边-多割问题为研究对象,运用参数计算与复杂性理论对它们进行了深入而细致地研究,并分别在参数化边-多端割扩展问题的核心化和参数化边-多割问题的固定参数可解算法开发两个方面取得了一定的成果。在参数化边-多端割扩展问题的核心化方面,本文通过深入地观察和分析问题结构上的特点,首次证明了边超额至多为1的图中的边-多端割问题的NP难解性,并在此基础上还进一步提出了该问题的第一个局部核心化算法,进而得到了该问题关于超额至多为1的边的一个大小不超过6k的局部核,其中k为待删除的边的条数。该结果作为边-多端割问题的第一个核心化成果,其意义不仅在于它摆脱了对给定的终端集个数l的依赖,还在于它是参数k的一个线性式。因此,这一结果在实际应用当中是切实可行的,并且它也为人们进一步研究边-多端割问题的核心化指明了一个新的方向。在参数化边-多割问题的固定参数可解算法开发方面,本文提出了一个时间复杂度为O（min{（2l）l,k2l}2kn2）的固定参数可解算法,其中l为终端对的个数,k为待删除的边的条数。值得注意的是,本文中采取的是一种全新的图论方法来证明集合C={s1,t1,s2,t2,…,sl,tl}的任意一个极大恰当划分中所包含的终端集的个数m具有上界（?）。该证明方法较之以前文献中给出的证明要更加简单明了,并且对于集合C的大小等于和小于2l的情况都是适用的。此外,根据该问题自身的一些特点,还可以得到m的另外一个上界k+1。从而也就得到了m的一个更优的上界min{[√2l],k+1}.在此基础上,本文还进一步证明了至多2l个不同的终端的所有极大恰当划分的总数的上界为min{（2l）l,k2l},该结果较之以前的最好结果亦有一定程度的改进。最后,本文对以上两个问题的研究工作进行了总结,并对今后研究工作的方向进行了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 参数计算与复杂性理论基础
• 1.2.2 参数算法设计技术分类介绍
• 1.3 研究内容
• 1.3.1 参数化边-多端割扩展问题的局部核心化研究
• 1.3.2 参数化边-多割问题的固定参数可解算法的研究
• 1.4 研究意义
• 1.5 论文结构
• 第二章 参数化边-多端割扩展问题的局部核心化
• 2.1 引言
• 2.2 相关术语和引理
• 2.2.1 相关术语的定义
• 2.2.2 相关引理的证明
• 2.3 小超额边的局部核心化的有用性
• 2.3.1 "诡计"图及其性质引理
• 2.3.2 边超额至多为1的边-多端割问题的NP完全性
• 2.4 问题结构的两个简单观察
• 2.5 超额至多为1的边的局部核心化
• 2.5.1 简化规则一及相关分析
• 2.5.2 简化规则二及相关分析
• 2.5.3 局部核心化的时间复杂度分析
• 2.6 本章小结
• 第三章 参数化边-多割问题的固定参数可解算法
• 3.1 引言
• 3.2 参数化边-多端割扩展问题的固定参数可解算法
• 3.2.1 终端集的最远最小切割
• 3.2.2 参数化边-多端割扩展问题的算法及其证明
• 3.3 参数化边-多割问题的固定参数可解算法
• 3.3.1 参数化边-多割问题与参数化边-多端割扩展问题之间的联系
• 1,t₁,s₂,t₂,…,s₁,t₁}的极大恰当划分'>3.3.2 集合{s₁,t₁,s₂,t₂,…,s₁,t₁}的极大恰当划分
• 3.3.3 参数化边-多割问题的算法及其证明
• 3.4 本章小结
• 第四章 总结与展望
• 4.1 研究工作总结
• 4.2 进一步研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间主要的研究成果