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

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

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

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

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

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

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

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

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

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

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

網(wǎng)絡(luò)分層用于最短路問題的算法研究04-27

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

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