作者：骆伟忠 冯启龙 王建新 陈建二dg模型固定参数可解树分解动态规划
摘要：完全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为问题解的大小．
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
