国家自然科学基金(60373025)

作品数：15被引量：10H指数：2
导出分析报告
相关作者：李曙光李国君何志红亓兴勤王继强更多>>
相关机构：山东大学鲁东大学天津师范大学济南铁道职业技术学院更多>>
相关期刊：《山东大学学报（理学版）》《计算机工程与应用》《山东大学学报（工学版）》《应用数学》更多>>
相关主题：多部竞赛图多项式时间近似方案排序波分复用染色更多>>
相关领域：理学自动化与计算机技术更多>>
-
在结果中检索

检索结果分析

结果分析中...
共 条 记 录，以下是1-10
全选清除导出
参考文献引证文献引用追踪
视图：
排序：
局部几乎正则多部竞赛图中的分量共轭圈
《系统工程与电子技术》2009年第10期2513-2515,共3页何志红 李国君 李曙光 
国家自然科学基金(60373025)资助课题
一个n-部竞赛图是n-部完全图的一个定向。令V1,V2,…,Vn是n-部有向图D的部集。如果D中存在两个不相交的圈C和C′使得对于每一个i∈{1,2,…,n}都有Vi∩(V(C)∪V(C′))≠Φ,则称C和C′是D的一对分量共轭圈。针对多部竞赛图的共轭圈问题,...
关键词：运筹学 分量共轭圈 贪心算法 共轭圈 局部几乎正则的 多部竞赛图 
若干情形分组和覆盖Steiner问题的算法
《计算机工程与应用》2007年第18期30-31,共2页王继强 
国家自然科学基金(the National Natural Science Foundation of China under Grant No.60373025) 。
综合论述了理论计算机科学领域中两个密切相关的NP-困难问题:分组Steiner问题和覆盖Steiner问题的不同解决途径,并就其若干特殊情形设计了近似比更好的近似算法。
关键词：分组Steiner问题 覆盖Steiner问题 近似算法 
工件尺寸不同的并行机批调度问题被引量：1
《山东大学学报（理学版）》2007年第4期63-66,共4页杨振光 李曙光 王秀红 
国家自然科学基金资助项目(60373025)
考虑并行批加工机上不同尺寸工件的调度问题;目标是极小化最大完工时间.给出了一个(2+ε)-近似算法,ε>0可以任意小.
关键词：近似算法 调度理论 批加工 最大完工时间 
二分图中含有大圈的2-因子
《山东大学学报（理学版）》2007年第4期28-31,38,共5页高云澍 李国君 
国家自然科学基金资助项目(60373025)
设G=(V1,V2;E)是一个二分图,其顶点数目满足|V1|=|V2|=n(k+1)s+1,s和k是满足s 3并且k 1的两个正整数.定义σ1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ1,1(G)2「(1-1s)n﹁+2,则G有一个2-因子包含至少k个圈,使得每个...
关键词：均衡二分图 圈 2-因子 
波分复用星形单跳网中3信道的传输调度问题被引量：1
《山东大学学报（理学版）》2007年第2期46-50,55,共6页戴珍香 李曙光 亓兴勤 
国家自然科学基金资助项目(60373025)
考虑波分复用星形单跳网中的数据包传输调度问题,假定诸发送机频率可调,而接收机频率固定.当m 2时,这一调度问题是NP-完备的,m表示所拥有的信道数目.对目前所知最好的一个2-近似算法进行了精细的分析,证明了m=3时,该算法近似比为74,并...
关键词：波分复用 星形网 单跳 数据包传输调度 调谐时延 近似算法 最坏情形分析 
含有一个6-圈的共轭圈问题
《计算机工程与应用》2006年第32期12-13,共2页何志红 李国君 马立杰 
国家自然科学基金资助项目(60373025)。
Yeo于1999年提出猜想:每一个至少有8个点的c-部(c≥4)正则竞赛图D包含一对不相交的长分别为t和｜V(D)｜-t的共轭圈,其中t∈｛3,4,…,｜V(D)｜-t｝。文章证明当c≥9时猜想对于t=6是成立的。
关键词：共轭圈 正则的 多部竞赛图 
交货期窗口待定情况下的平行机排序问题被引量：1
《山东大学学报（工学版）》2006年第5期99-101,共3页赵洪銮 韩国勇 
国家自然科学基金资助项目(60373025)
考虑多个工件在平行机上加工的生产调度问题,这些工件相互独立且有相同的交货期窗口,但交货期窗口的位置待定,其目标是最小化提前和延误的赋权工件数及交货期窗口定位费用的和.本文给出了这个强NP-困难问题的一个多项式时间近似序列(PTAS).
关键词：平行机 交货期窗口 提前 延误 
正则多部竞赛图中的分量共轭圈
《计算机工程与应用》2006年第17期7-8,共2页何志红 李国君 
国家自然科学基金资助项目(编号:60373025)
竞赛图的共轭圈问题已经完全解决,而关于多部有向图的共轭圈问题仍然是一个open问题。Yeo于1999年提出正则多部竞赛图包含共轭圈的猜想。论文根据分量共轭圈(componentwisecomplementarycycles)的定义,证明了:如果D是一个正则的n-部竞赛...
关键词：分量共轭圈 正则的 多部竞赛图 
基于设施选址问题的费用分配问题的近似算法被引量：5
《计算机工程与应用》2006年第13期13-14,32,共3页王继强 李国君 
国家自然科学基金资助项目(编号:60373025;10271065)
许多有着重要理论和应用价值的最优化问题在算法复杂性上都是NP-hard的,其解决方法之一是近似算法。论文研究了与设施选址问题密切相关的费用分配问题,并利用原始与对偶线性规划的思想和无容量设施选址问题的一个1.52-近似算法[1]给出...
关键词：设施选址 费用分配 近似算法 原始与对偶规划 
圈中t-区间的k-染色问题
《山东大学学报（理学版）》2006年第6期40-42,共3页李曙光 白淑岩 何志红 亓兴勤 
国家自然科学基金资助项目(60373025);天津市教委科技发展基金资助项目(20051519)
考虑客户请求在圈中实现的问题.每个请求联系着一个t-区间,由圈上至多t(t 1)个区间构成.要实现一个请求,需选择它所对应的t-区间中的一个区间并为其安排k种颜色中的一种.任意两个选定的区间如果在圈上有公共边,则不能得到同一种颜色.对...
关键词：圈 t-区间 k-染色 近似算法 
全选清除导出
共2页<12>
检索报告 对象比较 聚类工具 使用帮助 返回顶部