摘要：完全p-支配集是一个著名的NP-难问题，在无线传感网络中被用于构建无线传感节点的自我保护网络．该文主要研...完全p-支配集是一个著名的NP-难问题，在无线传感网络中被用于构建无线传感节点的自我保护网络．该文主要研究完全P-支配集在DG（Disk Graph）模型及其特殊模型上的参数复杂性及参数算法设计．首先证明完全p-支配集在顶点度受限的UDG（Unit Disk Graph）上仍是NP-难的．为了深入理解完全p-支配集在UDG模型上的难解性根源，利用参数化规约进一步研究了完全p-支配集在UDG上的参数复杂性．基于难解性根源的分析，最后利用树分解技术和动态规划技术，针对平面图（一种特殊DG模型）上的完全p-支配集，设计了一个时间为O（（2p＋2）^19.1·√kK^3n＋n^3）的精确算法，其中n为给定实例中的顶点个数，k为问题解的大小．显示全部
摘要：二次分配问题QAP（quadratic assignment problem）的变种问题是当前的研究热点．实际应用中存在一类不能用...二次分配问题QAP（quadratic assignment problem）的变种问题是当前的研究热点．实际应用中存在一类不能用QAP及其现有变种描述的问题，该类问题在QAP问题的基础上增加了额外的约束条件：将设备分为黑白两色，其中白色设备要求与至少一个黑色设备的距离不超过预定阈值．文章将之定义为黑白二次分配问题BWQAP（Black and White QAP）．文章首先分析了它的计算复杂性，指出该问题是NP-难解问题，不存在ε-近似度的多项式时间近似算法（ε〉0）．同时证明了其可行解的存在性与黑白图上的支配集问题等价，也属于NP-难解问题．为了能在可接受的时间内得到大规模实例质量可接受的近似解，提出了一种求解BWQAP的启发式算法GFO．该算法利用QAP现有算法得到初始解，然后利用局部搜索策略完成解的可行化和优化．大量实验表明，该启发式算法能够有效地求解BWQAP问题的实例．显示全部
