计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
9期
1868-1879
,共12页
骆伟忠%冯启龙%王建新%陈建二
駱偉忠%馮啟龍%王建新%陳建二
락위충%풍계룡%왕건신%진건이
完全p-支配集%DG模型%固定参数可解%树分解%动态规划
完全p-支配集%DG模型%固定參數可解%樹分解%動態規劃
완전p-지배집%DG모형%고정삼수가해%수분해%동태규화
total p-dominating set%disk graphs%fixed parameter tractable%tree decomposition%dynamic programming
完全p-支配集是一个著名的NP-难问题,在无线传感网络中被用于构建无线传感节点的自我保护网络.该文主要研究完全p-支配集在DG(Disk Graph)模型及其特殊模型上的参数复杂性及参数算法设计.首先证明完全p-支配集在顶点度受限的UDG(Unit Disk Graph)上仍是NP-难的.为了深入理解完全p-支配集在UDG模型上的难解性根源,利用参数化规约进一步研究了完全p支配集在UDG上的参数复杂性.基于难解性根源的分析,最后利用树分解技术和动态规划技术,针对平面图(一种特殊DG模型)上的完全p-支配集,设计了一个时间为O((2p+2)19.1·√kk3n+n3)的精确算法,其中n为给定实例中的顶点个数,k为问题解的大小.
完全p-支配集是一箇著名的NP-難問題,在無線傳感網絡中被用于構建無線傳感節點的自我保護網絡.該文主要研究完全p-支配集在DG(Disk Graph)模型及其特殊模型上的參數複雜性及參數算法設計.首先證明完全p-支配集在頂點度受限的UDG(Unit Disk Graph)上仍是NP-難的.為瞭深入理解完全p-支配集在UDG模型上的難解性根源,利用參數化規約進一步研究瞭完全p支配集在UDG上的參數複雜性.基于難解性根源的分析,最後利用樹分解技術和動態規劃技術,針對平麵圖(一種特殊DG模型)上的完全p-支配集,設計瞭一箇時間為O((2p+2)19.1·√kk3n+n3)的精確算法,其中n為給定實例中的頂點箇數,k為問題解的大小.
완전p-지배집시일개저명적NP-난문제,재무선전감망락중피용우구건무선전감절점적자아보호망락.해문주요연구완전p-지배집재DG(Disk Graph)모형급기특수모형상적삼수복잡성급삼수산법설계.수선증명완전p-지배집재정점도수한적UDG(Unit Disk Graph)상잉시NP-난적.위료심입리해완전p-지배집재UDG모형상적난해성근원,이용삼수화규약진일보연구료완전p지배집재UDG상적삼수복잡성.기우난해성근원적분석,최후이용수분해기술화동태규화기술,침대평면도(일충특수DG모형)상적완전p-지배집,설계료일개시간위O((2p+2)19.1·√kk3n+n3)적정학산법,기중n위급정실례중적정점개수,k위문제해적대소.
