论文部分内容阅读
连通支配集问题在网络广播上有着广泛的应用，本文引入测度函数的概念，提出了带测度函数的连通支配集问题（CDS（F）），使得它具有更广的应用范围。文中首先给出问题的形式定义，证明了它在各种情形下的NP完全性，并给出多项式时间的近似算法，它的近似度为Ln△＋3（△为图中顶点的最大度数）。
带测度函数的连通支配集问题
【摘 要】
：
连通支配集问题在网络广播上有着广泛的应用，本文引入测度函数的概念，提出了带测度函数的连通支配集问题（CDS（F）），使得它具有更广的应用范围。文中首先给出问题的形式定义，证明了它在
【机 构】
：
复旦大学计算机科学与工程系智能信息处理开放实验室
【出 处】
：
计算机科学
【发表日期】
：
2006年1期
【基金项目】
：
本文工作得到科技部基金（No.2001CCA03000）,国家自然科学基金（No.60273045）.上海科学技术发展基金（No.025115032）的支持.
其他文献
利用主成分分析法构建了一个管理利率风险的三因素久期模型，该模型可以计算相应的主成分久期。通过实证比较了该方法与Fisher-Weil久期的差异，发现不同期限的债券组合所受到的
建立了整个医院病床设置系统的仿真模型——多队列、多服务台并联的排队系统，分析了系统的结构特征。结合一个具体实例，利用统计方法确定出模型的运行参数。在Arena仿真环境下，
从行为距离的角度分析管理中的行为难题，应用泛函分析方法构建了行为赋泛空间模型以友相应的行为距离测度三维欧氏空间模型，为行为难题的解决提供了一个新的视角，为探寻组织和谐
从最小化期望损失的角度建立了季节性商品的最优定价模型,并采用粒子群算法进行求解。结合具体算例,根据不同库存量、库存量和折扣价的不同组合,分别获得达到最小期望损失的最优定价,可以很好地解释模型所具有的经济意义。对仿真结果的分析表明:粒子群算法不仅能灵活、简便地获得多种情况下的最优定价,而且反映了最优定价在库存量和折扣价不同组合时的变化规律,从而为销售商确定最优价格提供建议。因此,应用粒子群算法求解季
在简要地介绍GMDH算法的基础上,讨论了基于自组织算法的股市预测问题.建立带移动平均的预测模型,使预测值可以逐个地得到.以上证指数为应用实例,实验结果表明了GMDH算法在股
提出一种基于系统分析的故障树自动生成方法.首先,建立描述元部件因果模型及控制回路因果模型的数据库.然后,利用控制系统流程图和邻接矩阵确定系统中独立元部件、控制回路以
目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的