圖的部分控制集問題的修正 Greedy算法

部分控制集問題是對于給定的頂點賦權圖G=(V,E;c)和正整數(shù)K,尋找圖G一個頂點子集T,使得在其控制下的頂點個數(shù)不小于K且T中頂點權和達到最小.本文討論了部分控制集問題的NP-困難性;給出了該問題的一種修正Greedy近似算法,并對其近似度H(K)給出了證明.

作 者： 丁玲玲 方奇志 DING Ling-ling FANG Qi-zhi   作者單位： 中國海洋大學,數(shù)學系,山東,青島,266071  刊 名： 運籌與管理  ISTIC PKU 英文刊名： OPERATIONS RESEARCH AND MANAGEMENT SCIENCE  年，卷(期)： 2007 16(5)  分類號： O224 O157.6  關鍵詞： 運籌學   圖的控制集   近似算法   NP-困難  

【圖的部分控制集問題的修正 Greedy算法】相關文章：

機場停機位分配問題的圖著色模型及其算法04-26

基于修正因子智能權函數(shù)的汽車ABS模糊控制算法仿真研究04-27

多層次圖排序算法及其在圖剖分中的應用04-26

飛艇壓力控制系統(tǒng)的算法設計與仿真04-27

微型渦噴發(fā)動機控制算法研究04-26

紅外地球敏感器測量值修正算法及其應用研究04-27

高分辨率壓力修正算法在全速流動中的研究與應用04-26

網絡分層用于最短路問題的算法研究04-27

一類優(yōu)化問題的快速收斂算法04-26

水環(huán)境逆邊界逆動態(tài)混合控制精確算法04-27