位置：成果数据库 > 期刊 > 期刊详情页
若干情形分组和覆盖Steiner问题的算法
  • ISSN号：1002-8331
  • 期刊名称：《计算机工程与应用》
  • 时间：0
  • 分类：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
  • 作者机构：[1]山东大学数学与系统科学学院,济南250100, [2]山东财政学院数理与统计学院,济南250014
  • 相关基金：国家自然科学基金（the National Natural Science Foundation of China under Grant No.60373025）
作者： 王继强[1,2]
关键词： 分组Steiner问题, 覆盖Steiner问题, 近似算法, group Steiner problem, covering Steiner problem, approximation algorithm
中文摘要：

综合论述了理论计算机科学领域中两个密切相关的NP-困难问题：分组Steiner问题和覆盖Steiner问题的不同解决途径．并就其若干特殊情形设计了近似比更好的近似算法。

英文摘要：

We review different avenues to solve two closely-related NP-hard problems in theoretical computer science,the group Steiner problem and the covering Steiner problem,and design improved approximation algorithm for some special cases of them.

同期刊论文项目
近似算法的设计与分析
期刊论文 44
同项目期刊论文
An asymptotically optimal algo
Batch scheduling with a common
A PTAS for Semiconductor Burn-
正则多部竞赛图中的分量共轭圈
A PTAS for the scheduling and
A PTAS for Embedding Hypergrap
Detecting Uber-operon in proka
Minimizing makespan on a singl
Minimizing Total Weighted Comp
A linear-time algorithm for co
Minimizing total completion ti
基于设施选址问题的费用分配问题
Two feedback problems for grap
含有一个6-圈的共轭圈问题
On connected [g, f+1]-factors
A faster algorithm for genomic
Minimizing maximum lateness on
A linear time algorithm for th
Sorting signed permutations by
Proof of Chvatal’s conjecture
Minimizing makespan with relea
Unbounded batch scheduling with a common due window on a single machine
基于翻转和删除形式的染色体完美重组
二分图中含有大圈的2-因子
树的k-分支限制控制数的一个下界
交货期窗口待定情况下的平行机排序问题
二部图中包含六圈的度条件
二元序列的赋权对换排序问题
多纤波分复用链网与环网中的利润极大化问题
环网络中的呼叫接纳控制
圈中t-区间的k-染色问题
波分复用星形单跳网中3信道的传输调度问题
工件尺寸不同的并行机批调度问题
基因组重组问题的一个更快算法
最小化提前／延误赋权工件数及时窗惩罚的排序问题
求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS
极小化最大完工时间的单机分批加工问题
基于设施选址问题的费用分配问题的近似算法
极小化加权完工时间和的无界批量机器并行调度问题
局部几乎正则多部竞赛图中的分量共轭圈
Prospectous for Embedding Hypergraph in a Cycle
计算有向基因组圈图的连通分支的有效算法
期刊信息
  • 《计算机工程与应用》
  • 北大核心期刊（2014版）
  • 主管单位:中国电子科技集团公司
  • 主办单位:华北计算技术研究所
  • 主编：怀进鹏
  • 地址：北京市海淀区北四环中路211号北京619信箱26分箱
  • 邮编：100083
  • 邮箱：ceaj@vip.163.com
  • 电话：
  • 国际标准刊号：ISSN：1002-8331
  • 国内统一刊号：ISSN：11-2127/TP
  • 邮发代号:82-605
  • 获奖情况:
  • 1. 2012年首批获得中国学术文献评价中心发布的 “...,2. 2001年获得新闻出版署“中国期刊方阵双效期刊”,3. 2008年首批入选国家科技部“中国精品科技期刊...,4.2003年-2011年连续获得工业和信息化部期刊最高...
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,波兰哥白尼索引,美国剑桥科学文摘,英国科学文摘数据库,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:97887