位置：成果数据库 > 期刊 > 期刊详情页
顶点覆盖问题线性内核算法
  • ISSN号：1000-1239
  • 期刊名称：《计算机研究与发展》
  • 时间：0
  • 分类：PP301.6[天文地球]
  • 作者机构：[1]复旦大学信息工程学院计算机系,上海,200433 复旦大学信息工程学院计算机系,上海,200433 华东师范大学软件学院,上海,200062
  • 相关基金：上海重点学科建设基金项目(B412);国家自然科学基金项目(60496321,60703091)
作者： 蔡晟, Rudolf, Fleischer, 朱洪
关键词： 参数复杂性, 内核化, 线性内核, 定点覆盖
中文摘要：

参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).

同期刊论文项目
非规范知识的数学理论
期刊论文 164 会议论文 64 获奖 8 著作 1
公钥环境下零知识组合性研究
期刊论文 1 会议论文 8
同项目期刊论文
基于两阶段计数的用户关联挖掘
基于混合方式的贝叶斯网弧定向算法
基于MBR的拓扑、方位、尺寸结合的定性空间推理
一种基于特征重要度的文本分类特征加权方法
使用SAT求解器产生所有极小冲突部件集
混合语义约简和选择估值优化SPARQL
Greedy online frequency allocation in cellular networks
电子细胞Analog-Cell的并发机制
空间聚类在精准农业中的应用
部分可观察强规划中约减观察变量的研究
复杂网络聚类方法
基于图的分解与合并的静态事务调度算法
顶点覆盖变体问题的确定参数可解算法研究
一类弱支配集问题的近似算法
基于Hamming范数的XML流相关性估测算法
Progress in Computational Complexity Theory
An Improved Algorithm for Finding the Closest Pair of Points
Approximating the minimum weight weak vertex cover
A 1-Local Asymptotic 13/9- Competitive Algorithm for Multicoloring Hexagonal Graphs
Arbitrage opportunities across sponsored search markets
Design of a CIL Connector to SPIN
Tree Process Calculus.
Enumerating proofs of positive formulae
Weakly distributive domains(II)
On an open problem of Amadio and Curien: The finite antichain condition
Unconditional competitive auctions with copy and budget constraints
Proof search and counter model of positive minimal predicate logic
内点带权值的最小生成树算法
二人博弈问题中单一纳什均衡的搜索算法
基于后验概率的Markov逻辑网参数学习方法研究
结合似然关系模型和用户等级的协同过滤推荐算法
基于中间件的Web智能系统集成开发平台研究
动态系统基于模型诊断的研究进展与展望.
Analog-Cell: 一种新的电子细胞图形模型
Finding a Simple Nash Equilibrium
具有动态加权特性的关联规则算法
移动Agent计算理论和形式化方法研究
Analysis and Optimization for Mobile Agent Communication
A New Spatial Algebra for Road Network Moving Objects
一种高维空间数据的子空间聚类算法
一种不确定区域间的方向关系模型
定性方向关系模型研究进展
模糊栅格区域的层次拓扑关系模型
基于区间值模糊集的模糊区域拓扑关系模型
Force-based Incremental Algorithm for Mining Community Structure in Dynamic Network
Research of Logistics Transport Costs Computing in Automobile Industry.
A Novel Method of Model-based Diagnosis by Propagating Failure Value
Analog-Cell：一种新的电子细胞图形模型
A hierarchy of behavioral equivalences in the pi-calculus with noisy channels
含序信息的粗集方法研究
基于遗传与粒子群算法的Markov逻辑网学习研究
RSILP模型若干问题的研究
一种半监督K均值多关系数据聚类算法
一种特征加权的聚类算法框架
Preprocessing of Spatial Query in Distributed GIS
Logic of Integrating Metric Space and Time
基于模型检测的实时模型诊断方法
一种结合SE-tree计算所有极小碰集的方法
n取m不经意传输协议构造研究
关于吹雪机问题的改进近似算法
改进的二分法查找
图的支配集若干问题的研究
Oblivious Computation Proxy
带测度函数的连通支配集问题
计算复杂性理论部分进展简述
P2P结构与搜索机制研究
重复囚徒困境的学习和响应模型
Generalized Region Connection Calculus
Linguistic quantifiers modeled by Sugeno integrals
A theory of computation based on quantum logic
Catalyst-assisted Probabilistic Entanglement Transformation
Observability and decentralized control of fuzzy discrete event systems
Retraction and generalized extension of computing with words
Supervisory control of fuzzy discrete event systems
State-based control of fuzzy discrete event systems
A complete classification of topologic al relations using the 9-intersection method
On topological consistency and realization
混合系统基于模型诊断建模问题研究
基于分层任务网络的一致性规划方法
基于模型诊断中产生所有极小冲突集的新方法
一种基于ATMS的求解所有极小冲突集的新方法
A Method of Combing SE-tree to Compute all Minimal Hitting Sets
可用于诊断产生的计算碰集的新方法
On countable RCC models
On minimal models of the Region Connection Calculus
An algebra for moving objects
基于用户等级的协同过滤推荐算法
基于数据立方体的属性核计算方法
基于免疫进化算法的Bayesian网结构学习算法
CORS方法与规则生成算法GRs
The Existence of Quantum Entanglement Catalysts
Qualitative Spatial Representation and Reasoning: A Hierarchical Approach
种移动Agent 通信中本体信息调整方法
基于J2EE的交互式工作流管理系统
基于粗集理论的C3I信息融合性能评估方法研究
统计关系学习研究进展
一种基于移动代理的自主拍卖模型
多Agent协商研究
一种基于实例状态的工作流系统监控方法
传名调用演算的二值传递CPS变换
自组织分治求解分布式约束优化问题
一种基于模板的子句学习算法
Some Issues in Quantum Information Theory
结合度量空间和时间的逻辑
基于粒子群优化算法的Bayesian网络结构学习
面向不完备信息系统的粗糙集方法研究
数字农业时空信息管理平台
统计关系学习模型Markov逻辑网综述
结合拓扑和方位的定性空间推理方法
空间数据挖掘技术的研究现状与发展趋势
一种基于褶集的模糊区域可视化模型
基于协同产品数据管理理念的零部件子系统的设计
时空推理中自动生成复合表的通用算法
一种基于多Agent系统的饲料配方优化算法
RCC5与主方位关系结合的定性空间推理
一种Agent通信中逻辑意外信息转换方法
反期望模式的发现及其应用
一种预测商品销量及库存的新方法
基于信息熵的度量类间桥方法
一种新的汽车乘员分类视觉检测算法
工作流系统中一个基于多权角色和规则的条件化RBAC安全访问控制模型
聚类算法研究
中文网页语义标注：由句子到RDF表示
一种基于图形处理器的频繁模式挖掘算法
一种基于图形处理器的压缩单纯形方法
基于任务和角色访问控制模型分析与研究
基于VisualFoxpro软件设计中技术技巧的研究与实践
基于语义的主题爬行策略
期刊信息
  • 《计算机研究与发展》
  • 中国科技核心期刊
  • 主管单位:中国科学院
  • 主办单位:中国科学院计算技术研究所
  • 主编：徐志伟
  • 地址：北京市科学院南路6号中科院计算所
  • 邮编：100190
  • 邮箱：crad@ict.ac.cn
  • 电话：010-62620696 62600350
  • 国际标准刊号：ISSN：1000-1239
  • 国内统一刊号：ISSN：11-1777/TP
  • 邮发代号:2-654
  • 获奖情况:
  • 2001-2007百种中国杰出学术期刊，2008中国精品科...,中国期刊方阵“双效”期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,荷兰文摘与引文数据库,美国工程索引,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:40349