首页> 外文会议>Combinatorial Optimization and Applications >Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

【24h】

Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

机译：单位圆图中连接顶点覆盖的多项式时间近似方案

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

Connected Vertex Cover Problem (CVC) is an NP-hard problem. The currently best known approximation algorithm for CVC has performance ration 2. This paper gives the first Polynomial Time Approximation Scheme for CVC in Unit Disk Graph.

机译：连通顶点覆盖问题（CVC）是NP难题。当前最著名的CVC近似算法的性能等级为2。本文给出了单位盘图中CVC的第一个多项式时间近似方案。

著录项

来源
《Combinatorial Optimization and Applications 》|2008年|P.255-264|共10页
会议地点 St. Johns(CA);St. Johns(CA)
作者
Zhao Zhang; Xiaofeng Gao; Weili Wu;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术 ;
关键词
connected vertex cover; unit disk graph;

机译：连接的顶盖；单位圆盘图;

相似文献

外文文献
中文文献
专利

1. An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P3 Problem on Planar Graphs [J] . Jianhua Tu, Yongtang Shi Discussiones Mathematicae Graph Theory . 2019 ,第1期

机译：平面图上顶点覆盖P3问题的有效多项式时间逼近方案
2. A PTAS for the minimum weight connected vertex cover P-3 problem on unit disk graphs [J] . Wang Limin, Zhang Xiaoyan, Zhang Zhao, Theoretical computer science . 2015 ,第Null期

机译：单位磁盘图上用于连接顶点覆盖层P-3的最小重量问题的PTAS
3. PTAS for the minimum k-path connected vertex cover problem in unit disk graphs [J] . Xianliang Liu, Hongliang Lu, Wei Wang, Journal of Global Optimization . 2013 ,第2期

机译：PTAS用于单位圆图中的最小k路径连接的顶点覆盖问题
4. Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph [C] . Zhao Zhang, Xiaofeng Gao, Weili Wu International Conference on Combinatorial Optimization and Applications . 2008

机译：单元盘图中连接顶点盖的多项式时间近似方案
5. Vertex cover: Exact and approximation algorithms and applications. [D] . Kanj, Iyad. 2001

机译：顶点覆盖：精确和近似算法和应用。
6. Nonlinear electrocardiographic imaging using polynomial approximation networks [O] . Abhejit Rajagopal, Vincent Radzicki, Hua Lee, 2018

机译：使用多项式逼近网络的非线性心电图成像
7. PTAS for connected vertex cover in unit disk graphs [O] . Zhang Zhao, Gao Xiaofeng, Wu Weili 2009

机译：单位磁盘图中用于连接的顶点盖的PTAS

Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

摘要

著录项

相似文献

相关主题

期刊订阅