计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
21期
9-13
,共5页
连通支配集%有向图%参数算法%规约%近似算法
連通支配集%有嚮圖%參數算法%規約%近似算法
련통지배집%유향도%삼수산법%규약%근사산법
定义了有向图指定源点连通支配集问题.借助参数算法中的技术设计了针对该问题的规约规则,通过规约规则的实施来降低原问题的规模;随后又设计了近似算法在规约后的有向图中求出一个较小的连通支配集;最后结合规约规则带来的一些良好特性设计了优化规则,通过优化变换的实施进一步缩减由近似算法求得的连通支配集.不同模型随机图上的模拟实验表明这些规则和算法是有效的.
定義瞭有嚮圖指定源點連通支配集問題.藉助參數算法中的技術設計瞭針對該問題的規約規則,通過規約規則的實施來降低原問題的規模;隨後又設計瞭近似算法在規約後的有嚮圖中求齣一箇較小的連通支配集;最後結閤規約規則帶來的一些良好特性設計瞭優化規則,通過優化變換的實施進一步縮減由近似算法求得的連通支配集.不同模型隨機圖上的模擬實驗錶明這些規則和算法是有效的.
정의료유향도지정원점련통지배집문제.차조삼수산법중적기술설계료침대해문제적규약규칙,통과규약규칙적실시래강저원문제적규모;수후우설계료근사산법재규약후적유향도중구출일개교소적련통지배집;최후결합규약규칙대래적일사량호특성설계료우화규칙,통과우화변환적실시진일보축감유근사산법구득적련통지배집.불동모형수궤도상적모의실험표명저사규칙화산법시유효적.
