A Method for Simplifying Graph and Its Application Combined with GAs

李力; 罗予频; 胡东成

您当前的位置：

首页 >

文章列表页 >

A Method for Simplifying Graph and Its Application Combined with GAs

更新时间：2025-12-08

- A Method for Simplifying Graph and Its Application Combined with GAs
- Acta Electronica Sinica Issue 11, (1997)
- 作者机构：
  
  清华大学自动化系
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301.6
- Published：1997
- 稿件说明：
移动端阅览
[1]李力,罗予频,胡东成.一种图简化方法及其与遗传算法的混合运用[J].电子学报,1997(11):1-5+31.

李力, 罗予频, 胡东成. A Method for Simplifying Graph and Its Application Combined with GAs[J]. Acta Electronica Sinica, 1997, (11).
[1]李力,罗予频,胡东成.一种图简化方法及其与遗传算法的混合运用[J].电子学报,1997(11):1-5+31. DOI：

李力, 罗予频, 胡东成. A Method for Simplifying Graph and Its Application Combined with GAs[J]. Acta Electronica Sinica, 1997, (11). DOI：

摘要

本文提出了一种适用于图着色问题求解的图简化方法．在这种图简化方法中，图中度小于某个特定值的节点不断被去掉，把这种方法与各种图着色算法结合使用，能提高这些算法的效率．文中分析了应如何设定其特定值，并着重叙述了与遗传算法的混合运用．最后在给出仿真结果的同时，进一步指出了本方法同样适用于求最大全连接子图等其它图论问题．

Abstract

In this paper

we present a graph simplifying method which is fit for graph coloring problem. In this method

each node is deleted whenever its degree in the attained graph is less than a certain value. When graph coloring algorithms are combined with this simpliying method

their performances can be improved. We also exploit the schemes of setting the value and combining this method with GAs

and show the promising results of the simulation. Finally

it is pointed out that the method is also fit for other graph problems such as the largest clique

maximum independent set

etc.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Genetic Algorithm Based MIMO Equalization Parameter Optimization Technology for Mode-Division Multiplexed System

An Absorbing Structure Covering the Whole UHF Band

A Consortium Blockchain Based Reliable Task Offloading Approach in Edge Computing

An Approach to Multi-Path Coverage Testing Based on Key Edge Probability and Path Layer Proximity

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

Related Author

ZHAO Tian-feng

WEN Feng

FENG Bian-xia

WU Bao-jian

XU Bo

QIU Kun

WU Chang-ying

GAO Yang

Related Institution

Key Laboratory of Optical Fiber Sensing and Communication Networks, Ministry of Education, University of Electronics Science and Technology of China

School of Electronics and Information， Northwestern Polytechnical University

Key Laboratory for Novel Software Technology， Nanjing University

Guangdong Provincial Laboratory of Artificial Intelligence and Digital Economy

College of Big Data and Intelligent Engineering， Southwest Forestry University

⁰