DPBD-An Efficient Designing Method for the Approximation Algorithm of a kind of NP-Complete Problems

Yan Yong; Jin Chanmin

您当前的位置：

首页 >

文章列表页 >

DPBD-An Efficient Designing Method for the Approximation Algorithm of a kind of NP-Complete Problems

更新时间：2025-12-08

- DPBD-An Efficient Designing Method for the Approximation Algorithm of a kind of NP-Complete Problems
- Acta Electronica Sinica Issue 11, Pages: 63-68(1992)
- 作者机构：
  
  1. 华中理工大学计算机系
  2. 华中理工大学计算机系武汉430074
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：1992
- 稿件说明：
移动端阅览
[1]鄢勇,金灿明.DPBD——设计一类强NP-Complete问题近似算法的有效方法[J].电子学报,1992(11):63-68.

Yan Yong, Jin Chanmin. DPBD-An Efficient Designing Method for the Approximation Algorithm of a kind of NP-Complete Problems[J]. Acta Electronica Sinica, 1992, (11): 63-68.
[1]鄢勇,金灿明.DPBD——设计一类强NP-Complete问题近似算法的有效方法[J].电子学报,1992(11):63-68. DOI：

Yan Yong, Jin Chanmin. DPBD-An Efficient Designing Method for the Approximation Algorithm of a kind of NP-Complete Problems[J]. Acta Electronica Sinica, 1992, (11): 63-68. DOI：

摘要

本文针对一类强NP-Complete问题近似算法的设计问题

提出一种通用的设计策略DPBD

它通过一局部近似算法而获得一全局近似算法

并保证精度在一定范围内.最后

本文将DPBD应用于一著名的NP难度问题:平面Covering问题

对方法的有效性给予了证实.

Abstract

The paper devises a general designing method DPBD for the approximation algorithm of a kind of NP-complete problems. DPBD can get a global approximation algorithm from a local one and keep the precision to a definite range. At last

DPBD has been used to solve planar covering problem

thus the effectiveness of the method is Verified.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Research on Load Balancing of Distributed Control Plane in Polymorphic Network

An Efficient Algorithm of Information Recommendation Between Groups in Social Networks

Related Author

TU Hua-qing

LIU Shuo

FANG Xu-xin

MA Bo

LI Chuan-huang

ZHU Jun

ZOU Tao

HUANG Zhen-hua

Related Institution

Zhejiang Gongshang University

Zhijiang Lab

Department of Computer and Technology, Tongji University

The Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University

College of Information, Mechanical and Electrical Engineering, Shanghai Normal University

⁰