K条路的两个问题

来源 :云南民族大学学报：自然科学版 | 被引量 : 0次 | 上传用户：zkry123

【摘要】

：

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广--有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,

【作者】

：

王泽磊张同全

【机构】

：

云南大学数学系

【出处】

：

云南民族大学学报：自然科学版

【发表日期】

：

2005年2期

【关键词】

：

最小费用流 k条路偏差算法 minimum cost flow deviation algorithm k paths

【基金项目】

：

云南省自然科学基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

关于寻找有向连通图G=(V,E)的最小最大的k条弧不交路的问题是NP-完备的.研究这个问题的推广--有容量限制的k条路问题:①寻找k条路,使得k条路的费用之和尽可能小;②寻找k条路,使得k条路中最长的路的费用尽可能小.给出了问题①的一个最优算法,其复杂度为O(k| V|2),同时证明了该算法对于问题是k-近似的.

其他文献

完善司法制度实现司法公正——关于法官独立与错案责任追究

法官独立是实现司法公正的前提,但没有监督的权力会产生腐败;错案责任追究制度对我国的司法腐败确实起到了一定的遏制和惩戒的作用,推进了司法公正的进程.然而,其对法官独立

期刊

司法公正法官独立错案责任追究

糖尿病并发症患者50例临床分析

糖尿病是一种代谢内分泌疾病,近年来,随着社会经济条件的改善,人们生活水平及糖尿病检测水平的提高,糖尿病的发病率正逐年增加。本文对2008年6月至2009年6月在我科住院的50例

期刊

糖尿病并发症胰岛素中医内科学

三种中药水煎剂的体外抗菌试验研究新进展

目的评价黄连、黄芩、五倍子三种中药水煎剂对表皮葡萄球菌的体外抗菌作用。方法采用M-H琼脂稀释法对黄连等3种中药进行体外抗菌活性检测。结果五倍子对表皮葡萄球菌的抗菌活

期刊

表皮葡萄球菌抗感染药黄连黄芩五倍子

喷气织机控制器CAN通信接口设计及实现

提出了基于Win CE的喷气织机控制器CAN通信接口设计及实现的方法。设计了CAN通信接口的硬件电路，介绍了接口驱动程序的工作机制及开发环境，详细阐述了Win CE流接口驱动程序的开

期刊

WINDOWSCECAN总线流接口驱动喷气织机控制器Windows CE CAN bus Stream interface driver Air

居家过日子须防“电磁污染”

当人们尽情地享受着电视机、VCD、电脑、手机、电热水器、电饭煲等电气化设备带来的便利时,由此导致的电磁污染也在或多或少地损害着大家的身体健康.

期刊

电磁污染电气化设备预防合理使用

温室微灌技术与设备（上）

一、微灌的种类根据温室生产的特点,温室灌溉均采用微灌技术.微灌是利用微灌设备组装成微灌系统,将有压水输送分配到田间,通过灌水器以微小的流量湿润作物根部附近土壤的一

期刊

温室微灌技术设备系统组成

农业结构调整应坚持四项原则

期刊

农业结构调整原则经济效益优行可持续发展

K条路的两个问题

其他学术论文