位置：成果数据库 > 期刊 > 期刊详情页
奖励收集顶点覆盖问题的一个2-近似算法
  • ISSN号：1671-4628
  • 期刊名称：北京化工大学学报(自然科学版)
  • 时间：2014
  • 页码：120-123
  • 分类：O157.5[理学—数学;理学—基础数学]
  • 作者机构：[1]北京化工大学理学院
  • 相关基金：国家自然科学基金青年基金(11201021)
  • 相关项目：顶点覆盖k-路问题
作者： 杜俊峰|涂建华|
关键词： 组合优化, 奖励收集顶点覆盖问题, 迭代松弛方法, 近似算法
中文摘要：

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。

同期刊论文项目
顶点覆盖k-路问题
期刊论文 15
同项目期刊论文
On the Number of Paths, Independent Sets, and Matchings of Low Order in (5, 6)-Fullerene Graphs
An FPT algorithm for the vertex cover P4 problem
Rainbow numbers for matchings in plane triangulations
On the number of 5-matchings in boron-nitrogen fullerene graphs
A 2-approximation algorithm for the vertex cover P4 problem in cubic graphs
An Iterative Rounding 2-approximation Algorithm for the k-partial Vertex Cover Problem
On the Number of Paths, Independent Sets, and Matchings of Low Order in (5,6)-Fullerene Graphs
A fixed-parameter algorithm for the vertex cover P3 problem
The vertex cover P3 problem in cubic graphs
Inertia of complex unit gain graphs
The generalized 3-connectivity of star graphs and bubble-sort graphs
The unicyclic graphs with maximum degree resistance distance
The degree resistance distance of cacti
期刊信息
  • 《北京化工大学学报：自然科学版》
  • 北大核心期刊（2011版）
  • 主管单位:教育部
  • 主办单位:北京化工大学
  • 主编：刘振宇
  • 地址：北京市北三环东路15号
  • 邮编：100029
  • 邮箱：bhxbzr@126.com
  • 电话：010-64434926
  • 国际标准刊号：ISSN：1671-4628
  • 国内统一刊号：ISSN：11-4755/TQ
  • 邮发代号:82-657
  • 获奖情况:
  • 1999年教育部优秀科技期刊二等奖,1997年第二届全国科技期刊评比三等奖,1995年全国重点高校自然科学学报二等奖,中国期刊方阵“双效”期刊,首届高校优秀科技期刊,全国石化行业优秀期刊一等奖
  • 国内外数据库收录:
  • 美国化学文摘（网络版）,荷兰文摘与引文数据库,美国剑桥科学文摘,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）
  • 被引量:9420